Edge tree spanners

DOI10.1007/978-3-030-63072-0_16zbMath1479.05052OpenAlexW3135634383MaRDI QIDQ2056906

Luís Cunha, Fernanda Couto, Daniel F. D. Posner

Publication date: 8 December 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-63072-0_16

zbMATH Keywords

NP-completenesspolynomial time algorithmsline graphsgraph classestree \(t\)-spanneredge tree \(t\)-spanner

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Minimum \(t\)-spanners on subcubic graphs ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Hardness and efficiency on \(t\)-admissibility for graph operations

Cites Work

• Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs
• Tree \(t\)-spanners of a graph: minimizing maximum distances efficiently
• An Optimal Synchronizer for the Hypercube
• Tree Spanners
• P-Components and the Homogeneous Decomposition of Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Edge tree spanners