Hardness and efficiency on minimizing maximum distances in spanning trees

DOI10.1016/j.tcs.2020.06.012zbMath1453.68131OpenAlexW3037635482MaRDI QIDQ2197544

Fernanda Couto, Luís Cunha

Publication date: 1 September 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.06.012

zbMATH Keywords

\((2, 1)\)-chordal graphs\((k, \ell)\)-graphsstretch index3-admissibilitygraphs with few \(P_4\)sP vs NP-complete dichotomy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Strategies for generating tree spanners: algorithms, heuristics and optimal graph classes ⋮ Hardness and efficiency on \(t\)-admissibility for graph operations

Cites Work

• Unnamed Item
• Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms
• Spanners in sparse graphs
• Tree spanners for bipartite graphs and probe interval graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Characterization and recognition of tree 3-spanner admissible directed path graphs of diameter three
• Tree spanners on chordal graphs: complexity and algorithms
• Partitions of graphs into one or two independent sets and cliques
• Tree \(t\)-spanners of a graph: minimizing maximum distances efficiently
• Tree Spanners
• P-Components and the Homogeneous Decomposition of Graphs
• Advancing the Transposition Distance and Diameter through Lonely Permutations

This page was built for publication: Hardness and efficiency on minimizing maximum distances in spanning trees