Klíč na stromy - Tree spanner

A strom k-klíč (nebo jednoduše k-klíč) a graf ${displaystyle G}$ je překlenující podstrom ${displaystyle T}$ z ${displaystyle G}$ ve kterém je vzdálenost mezi každou dvojicí vrcholů maximálně ${displaystyle k}$ krát jejich vzdálenost v ${displaystyle G}$.

Známé výsledky

Na téma stromových klíčů je napsáno několik článků. Jeden z nich měl nárok Klíče na stromy^[1] napsali matematici Leizhen Cai a Derek Corneil, která zkoumala teoretické a algoritmické problémy spojené s klíče na stromy. Některé závěry z tohoto článku jsou uvedeny níže. ${displaystyle n}$ je vždy počet vrcholů grafu a ${displaystyle m}$ je jeho počet hran.

1. 1-klíčový strom, pokud existuje, je minimální kostra a lze jej najít v ${displaystyle {mathcal {O}} (mlog eta (m, n))}$ čas (z hlediska složitosti) pro vážený graf, kde ${displaystyle eta (m, n) = zbývá min. {imid log ^ {i} nleq m / noc}}$. Kromě toho každý přípustný vážený graf s 1 klíčem obsahuje jedinečný minimální kostru.
2. Lze zabudovat 2-stranový klíč ${displaystyle {mathcal {O}} (m + n)}$ čas a strom ${displaystyle t}$problém s klíčem je NP-kompletní pro jakékoli pevné celé číslo ${displaystyle t> 3}$.
3. Složitost pro nalezení minimálního klíče stromu v digrafu je ${displaystyle {mathcal {O}} ((m + n) cdot alfa (m + n, n))}$, kde ${displaystyle alfa (m + n, n)}$ je funkční inverzní k Ackermannova funkce
4. Minimální 1 klíč váženého grafu najdete v ${displaystyle {mathcal {O}} (mn + n ^ {2} log (n))}$ čas.
5. Pro jakékoli pevné racionální číslo ${displaystyle t> 1}$, je NP-úplné určit, zda vážený graf obsahuje stromový klíč, i když jsou všechny okrajové váhy kladná celá čísla.
6. Klíč stromu (nebo minimální klíč stromu) digrafu lze nalézt v lineárním čase.
7. Digraf obsahuje nejvýše jeden klíč na strom.
8. Kvazi-stromový klíč váženého digrafu najdete v ${displaystyle {mathcal {O}} (mlog eta (m, n))}$ čas.

Viz také

• Klíč na grafy
• Geometrický klíč

Reference

• Handke, Dagmar; Kortsarz, Guy (2000), „Klíče stromů pro podgrafy a související problémy s pokrýváním stromů“, Graficko-teoretické koncepty v informatice: 26. mezinárodní workshop, WG 2000 Konstanz, Německo, 15. – 17. Června 2000, sborník, Přednášky v informatice, 1928, str. 206–217, doi:10.1007/3-540-40064-8_20, ISBN  978-3-540-41183-3.