Древесный каркас

Древесный k-каркас^[1] (или просто k-каркас) графа ${\displaystyle G}$ — это остовное поддерево ${\displaystyle T}$ графа ${\displaystyle G}$, в котором расстояние между любой парой вершин не превосходит ${\displaystyle k}$-кратного расстояния в графе ${\displaystyle G}$.

Имеется несколько статей по теме древесных каркасов. Одну из них под заглавием Tree Spanners (Древесные Каркасы)^[2] написали математики Лейчжень Кай и Дерек Корнил, которые исследовали теоретические и алгоритмические проблемы, связанные с древесными каркасами. Некоторые из выводов этой статьи приведены ниже. Ниже ${\displaystyle n}$ везде обозначает число вершин графа, а ${\displaystyle m}$ является числом рёбер.

1. Древесный 1-каркас, если существует, является наименьшим остовным деревом и может быть найден за время ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$ (в терминах сложности) для взвешенных графов, где ${\displaystyle \beta (m,n)=\min \left\{i\mid \log ^{i}n\leqslant m/n\right\}}$. Более того, любой древесный 1-каркас взвешенного графа, если существует, содержит единственное минимальное остовное дерево.
2. Древесный 2-каркас может быть построен за линейное время ${\displaystyle {\mathcal {O}}(m+n)}$, а задача нахождения древесного ${\displaystyle t}$-каркаса является NP-полной для любого фиксированного целого ${\displaystyle t>3}$.
3. Сложность нахождения наименьшего древесного каркаса в орграфе равна ${\displaystyle {\mathcal {O}}((m+n)\cdot \alpha (m+n,n))}$, где ${\displaystyle \alpha (m+n,n)}$ является функцией, обратной функции Аккермана.
4. Наименьший древесный 1-каркас взвешенного графа может быть найден за время ${\displaystyle {\mathcal {O}}(mn+n^{2}\log(n))}$.
5. Для любого фиксированного рационального числа ${\displaystyle t>1}$ определение, содержит ли взвешенный граф древесный 1-каркас, является NP-полной задачей, даже если все веса рёбер заданы как целые положительные числа.
6. Орграф содержит максимум одни древесный каркас.
7. Квазидревесный каркас взвешенного орграфа может быть найден за время ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$ time.

• Геометрический остов

• Dagmar Handke, Guy Kortsarz. Tree spanners for subgraphs and related tree covering problems // Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000 Konstanz, Germany, June 15–17, 2000, Proceedings. — 2000. — Т. 1928. — С. 206–217. — (Lecture Notes in Computer Science). — ISBN 978-3-540-41183-3. — doi:10.1007/3-540-40064-8_20.
• Leizhen Cai, Derek G. Corneil. Tree Spanners. — 1995. — Т. 8, вып. 3. — С. 359–387. — doi:10.1137/S0895480192237403.