Hardness and efficiency on minimizing maximum distances in spanning trees

DOI10.1016/J.TCS.2020.06.012MaRDI QIDQ2197544zbMATH OpenOpenAlexFDO

Authors F. Couto, Luís Felipe Ignácio 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

3-admissibility\((2, 1)\)-chordal graphs\((k, \ell)\)-graphsgraphs with few \(P_4\)sP vs NP-complete dichotomystretch index

Mathematics Subject Classification ID

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

Recommendations

• Tree \(t\)-spanners of a graph: minimizing maximum distances efficiently
• On the maximal distance of spanning trees
• On the approximability of some maximum spanning tree problems
• On the approximability of some Maximum Spanning Tree Problems
• Minimum Diameter Spanning Trees and Related Problems
• The complexity of minimum ratio spanning tree problems
• On the minimum diameter spanning tree problem
• Approximating the degree-bounded minimum diameter spanning tree problem
• Approximating the degree-bounded minimum diameter spanning tree problem
• Computing a minimum-dilation spanning tree is NP-hard

Cites work

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

Cited in

(11)

• The realization problem for Euclidean minimum spanning trees is NP-hard
• Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs
• Hardness and efficiency on \(t\)-admissibility for graph operations
• Strategies for generating tree spanners: algorithms, heuristics and optimal graph classes
• Optimality characterization of the minimum stretch spanning tree problem for interval graphs
• New results on edge-coloring and total-coloring of split graphs
• Iterated local search with two strategies in the acceptance criterion for the tree t-spanner problem
• Filling some gaps on the edge coloring problem of split graphs
• Minimizing distances between vertices and edges through tree t-spanners
• Structural characterizations of tree t-spanners for graphs with few P₄'s and (0, )-graphs
• Minimizing distances between vertices and edges through tree \(t\)-spanners

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197544)