| Title:
|
Two linear time algorithms for MST on minor closed graph classes (English) |
| Author:
|
Mareš, Martin |
| Language:
|
English |
| Journal:
|
Archivum Mathematicum |
| ISSN:
|
0044-8753 (print) |
| ISSN:
|
1212-5059 (online) |
| Volume:
|
40 |
| Issue:
|
3 |
| Year:
|
2004 |
| Pages:
|
315-320 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
This article presents two simple deterministic algorithms for finding the Minimum Spanning Tree in $O(\vert V\vert +\vert E\vert )$ time for any non-trivial class of graphs closed on graph minors. This applies in particular to planar graphs and graphs of bounded genus. Both algorithms run on a pointer machine and they require no a priori knowledge of the structure of the class except for its density. Edge weights are only compared. (English) |
| Keyword:
|
minor closed graph classes |
| Keyword:
|
minimum spanning trees |
| MSC:
|
05C05 |
| MSC:
|
05C85 |
| MSC:
|
68R10 |
| idZBL:
|
Zbl 1116.05079 |
| idMR:
|
MR2107027 |
| . |
| Date available:
|
2008-06-06T22:44:07Z |
| Last updated:
|
2012-05-10 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/107914 |
| . |
| Reference:
|
[1] Borůvka O.: O jistém problému minimálním (About a Certain Minimal Problem).Práce mor. přírodověd. spol. v Brně, III, (1926), 37–58. Czech with German summary. |
| Reference:
|
[2] Frederickson G. N.: Data structures for on-line updating of minimum spanning trees.SIAM J. Comput. 14 (1985), 781–798. Zbl 0575.68068, MR 0807881 |
| Reference:
|
[3] Fredman M., Willard D. E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths.In Proceedings of FOCS’90 (1990), 719–725. |
| Reference:
|
[4] Graham R. L., Hell P.: On the history of the minimum spanning tree problem.Ann. Hist. Comput. 7 (1985), 43–57. Zbl 0998.68003, MR 0783327 |
| Reference:
|
[5] Chazelle B.: A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity.J. ACM 47 (2000), 1028–1047. Zbl 1094.68606, MR 1866456 |
| Reference:
|
[6] Karger D. R., Klein P. N., Tarjan R. E.: Linear expected-time algorithms for connectivity problems.J. ACM 42 (1995), 321–328. MR 1409738 |
| Reference:
|
[7] Matsui T.: The Minimum Spanning tree Problem on a Planar Graph.Discrete Appl. Math. 58 (1995), 91–94. Zbl 0823.05024, MR 1323024 |
| Reference:
|
[8] Nešetřil J.: Some remarks on the history of MST-problem.Arch. Math. (Brno) 33 (1997), 15–22. MR 1464297 |
| Reference:
|
[9] Nešetřil J., de Mendez P. O.: Colorings and Homomorphism of Minor Closed Classes.To appear in Pollack-Goodman Festschrift, Springer Verlag, 2002. Zbl 1071.05526, MR 2038495 |
| Reference:
|
[10] Nešetřil J., Milková E., Nešetřilová H.: Otakar Borůvka on Minimum Spanning Tree Problem.Discrete Math. 233(1–3) (2001), 3–36. Zbl 0999.01019 |
| Reference:
|
[11] Pettie S.: Finding minimum spanning trees in $O(m\alpha (m,n))$ time.Tech Report TR99-23, Univ. of Texas at Austin, 1999. |
| Reference:
|
[12] Pettie S., Ramachandran V.: An Optimal Minimum Spanning Tree Algorithm.In Proceedings of ICALP’2000, 49–60, Springer Verlag, 2000. Zbl 0973.68534, MR 1795885 |
| Reference:
|
[13] Tarjan R. E.: Data structures and network algorithms.44 CMBS-NSF Regional Conf. Series in Appl. Math. SIAM, 1983. Zbl 0584.68077, MR 0826534 |
| . |
