×

zbMATH — the first resource for mathematics

On minimum average stretch spanning trees in polygonal 2-trees. (English) Zbl 1310.05059
Summary: A spanning tree of an unweighted graph is a minimum average stretch spanning tree if it minimizes the ratio of sum of the distances in the tree between the end vertices of the graph edges and the number of graph edges. For a polygonal 2-tree on \(n\) vertices, we present an algorithm to compute a minimum average stretch spanning tree in \(O(n \log n)\) time. This algorithm also finds a minimum fundamental cycle basis in polygonal 2-trees. We show that there is a unique minimum cycle basis in a polygonal 2-tree and it can be computed in linear time.

MSC:
05C05 Trees
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N.; Karp, R. M.; Peleg, D.; West, D., A graph-theoretic game and its application to the k-server problem, SIAM J. Comput., 24, 78-100, (1995) · Zbl 0818.90147
[2] Bodlaender, H. L., A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-2, 1-45, (1998) · Zbl 0912.68148
[3] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to algorithms, (2009), MIT Press · Zbl 1187.68679
[4] Deo, N.; Prabhu, G.; Krishnamoorthy, M. S., Algorithms for generating fundamental cycles in a graph, ACM Trans. Math. Software, 8, 26-42, (1982) · Zbl 0477.68070
[5] Diestel, R., Graph theory, (2010), Springer · Zbl 1204.05001
[6] Ducharme, M.; Labelle, G.; Lamathe, C.; Leroux, P., A classification of outerplanar k-gonal 2-trees, (19th Intern. Conf. on FPSAC, (2007)), Appeared as Poster
[7] Emek, Y., k-outerplanar graphs, planar duality, and low stretch spanning trees, Algorithmica, 61, 1, 141-160, (2011) · Zbl 1223.05040
[8] Emek, Y.; Peleg, D., A tight upper bound on the probabilistic embedding of series-parallel graphs, SIAM J. Discrete Math., 23, 4, 1827-1841, (2009) · Zbl 1207.68231
[9] Eppstein, D., Parallel recognition of series-parallel graphs, Inform. and Comput., 98, 1, 41-55, (1992) · Zbl 0754.68056
[10] Fowler, T.; Gessel, I.; Labelle, G.; Leroux, P., The specification of 2-trees, Adv. in Appl. Math., 28, 2, 145-168, (2002) · Zbl 1003.05054
[11] Galbiati, G.; Rizzi, R.; Amaldi, E., On the approximability of the minimum strictly fundamental cycle basis problem, Discrete Appl. Math., 159, 4, 187-200, (2011) · Zbl 1210.05067
[12] Hubicka, E.; Sysło, M., Minimal bases of cycles of a graph, (Recent Advances in Graph Theory, Second Czech Symposium in Graph Theory, (1975), Academia Prague), 283-293 · Zbl 0325.05115
[13] Kavitha, T.; Liebchen, C.; Mehlhorn, K.; Michail, D.; Rizzi, R.; Ueckerdt, T.; Zweig, K. A., Cycle bases in graphs characterization, algorithms, complexity, and applications, Comput. Sci. Rev., 3, 4, 199-243, (2009) · Zbl 1301.05195
[14] Koh, K. M.; Teo, C. P., Chromaticity of series-parallel graphs, Discrete Math., 154, 1-3, 289-295, (1996) · Zbl 0856.05035
[15] Labelle, G.; Lamathe, C.; Leroux, P., Labelled and unlabelled enumeration of k-gonal 2-trees, J. Combin. Theory Ser. A, 106, 2, 193-219, (2004) · Zbl 1042.05007
[16] Leydold, J.; Stadler, P. F., Minimal cycle bases of outerplanar graphs, Electron. J. Combin., 209-222, (1998) · Zbl 0895.05032
[17] Liebchen, C.; Wünsch, G., The zoo of tree spanner problems, Discrete Appl. Math., 156, 569-587, (2008) · Zbl 1176.90504
[18] MacLane, S., A combinatorial condition for planar graphs, Fund. Math., 28, 22-32, (1937) · Zbl 0015.37501
[19] Omoomi, B.; Peng, Y.-H., Chromatic equivalence classes of certain generalized polygon trees, III, Discrete Math., 271, 1-3, 223-234, (2003) · Zbl 1021.05035
[20] Peng, Y.-H.; Little, C. H.C.; Teo, K. L.; Wang, H., Chromatic equivalence classes of certain generalized polygon trees, Discrete Math., 172, 1-3, 103-114, (1997) · Zbl 0883.05058
[21] Ramachandran, V., Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity, (1992), Morgan-Kaufmann
[22] Stadler, P. F., Minimum cycle bases of halin graphs, J. Graph Theory, 43, 150-155, (2000) · Zbl 1022.05041
[23] Sysło, M.; Prokurowski, A., On halin graphs, (Graph Theory, Proc. Conf., Lagow/Poland, Lecture Notes in Math., vol. 1018, (1983), Springer New York), 248-256
[24] West, D. B., Introduction to graph theory, (2001), Prentice Hall
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.