Structural characterizations of tree t-spanners for graphs with few P4’s and (0, ℓ)-graphs

Open Access

Issue		RAIRO-Oper. Res. Volume 59, Number 2, March-April 2025


Page(s)		835 - 846
DOI		https://doi.org/10.1051/ro/2025012
Published online		14 March 2025

A. Barboza Queiroz, Dominaç˜ao Total e Aliança Defensiva Global em Grafos Clique Expandidos. Master’s thesis, University of Rio de Janeiro (2020). [Google Scholar]
A. Brandstadt, F.F. Dragan, H.-O. Le, V.B. Le and R. Uehara, Tree spanners for bipartite graphs and probe interval graphs. Algorithmica 47 (2007) 27–51. [CrossRef] [MathSciNet] [Google Scholar]
L. Cai and D.G. Corneil, Tree spanners. SIAM J. Discrete Math. 8 (1995) 359–387. [CrossRef] [MathSciNet] [Google Scholar]
D.G. Corneil, H. Lerchs and L.S. Burlingham, Complement reducible graphs. Discrete Appl. Math. 3 (1981) 163–174. [CrossRef] [MathSciNet] [Google Scholar]
F. Couto and L. Cunha, Hardness and efficiency on minimizing maximum distances for graphs with few P4’s and (k, l)-graphs. Electron. Notes Theor. Comp. Sci. 346 (2019) 355–367. [CrossRef] [Google Scholar]
F. Couto and L. Cunha, Hardness and efficiency on minimizing maximum distances in spanning trees. Theor. Comp. Sci. 838 (2020) 168–179. [CrossRef] [Google Scholar]
F. Couto and L.F.I. Cunha, Hardness and efficiency on t-admissibility for graph operations. Discrete Appl. Math. 304 (2021) 342–348. [CrossRef] [MathSciNet] [Google Scholar]
F. Couto, L. Cunha and D. Posner, Edge tree spanners, in Vol. AIRO Springer Series of 18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (2020) 1–12. [Google Scholar]
F. Couto, L.F.I. Cunha, D. Juventude and L. Santiago, Strategies for generating tree spanners: algorithms, heuristics and optimal graph classes. Inf. Process. Lett. 177 (2022) 106265. [CrossRef] [Google Scholar]
L. Cunha, E. Marciano, A. Moraes, L. Santiago and C. Santos, New parallelism and heuristic approaches for generating tree t-spanners in graphs. Concurrency Comput. Pract. Exp. (2024) 1–36. DOI: 10.1002/cpe.8106. [Google Scholar]
L. Cunha, L. Santiago and F. Souza, Graph admissibility: case generation and analysis by learning models. J. Comput. Sci. 78 (2024) 102281. [CrossRef] [Google Scholar]
R.L.O. da Silva, Aspectos Computacionais de Convexidade em Grafos de Linha. Ph.D. thesis, University of Rio de Janeiro (2021). [Google Scholar]
Y. Emek and D. Peleg, Approximating minimum max-stretch spanning trees on unweighted graphs, in 15th ACM-SIAM Symposium on Discrete Algorithms (2004) 261–270. [Google Scholar]
O. Favaron, Irredundance in inflated graphs. J. Graph Theory 28 (1998) 97–104. [CrossRef] [MathSciNet] [Google Scholar]
S. Foldes and P.L. Hammer, Split graphs having dilworth number two. Can. J. Math. 29 (1977) 666–672. [CrossRef] [Google Scholar]
V. Giakoumakis, F. Roussel and H. Thuillier, On P₄-tidy graphs. Discrete Math. Theor. Comp. Sci. 1 (1997). DOI: 10.46298/dmtcs.232. [Google Scholar]
R. Gómez, F.K. Miyazawa and Y. Wakabayashi, Tree 3-spanners on generalized prisms of graphs, in Latin American Symposium on Theoretical Informatics. Springer (2022) 557–573. [Google Scholar]
B. Jamison and S. Olariu, A tree representation for P₄-sparse graphs. Discrete Appl. Math. 35 (1992) 115–129. [CrossRef] [MathSciNet] [Google Scholar]
B. Jamison and S. Olariu, P-components and the homogeneous decomposition of graphs. SIAM J. Discrete Math. 8 (1995) 448–463. [CrossRef] [MathSciNet] [Google Scholar]
L. Lin and Y. Lin, Optimality computation of the minimum stretch spanning tree problem. Appl. Math. Comput. 386 (2020) 125502. [MathSciNet] [Google Scholar]
D. Peleg and A.A. Sch¨affer, Graph spanners. J. Graph Theory 13 (1989) 99–116. [CrossRef] [MathSciNet] [Google Scholar]
D. Peleg and J. Ullman, An optimal synchronizer for the hypercube, in Proceedings of the 6th ACM Symposium on Principles of Distributed Computing. Vancouver (1987) 77–85. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.