Edge tree spanners

DOI10.1007/978-3-030-63072-0_16MaRDI QIDQ2056906zbMATH OpenOpenAlexFDO

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

edge tree \(t\)-spannergraph classesline graphsNP-completenesspolynomial time algorithmstree \(t\)-spanner

Mathematics Subject Classification ID

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

Recommendations

• Tree Spanners
• scientific article; zbMATH DE number 434687
• Edge-magic trees
• Spanning trees whose stems are spiders
• scientific article; zbMATH DE number 1933253
• scientific article; zbMATH DE number 431364
• scientific article; zbMATH DE number 3906515
• Spanning trees in a cactus
• Spanning Trees with Many Leaves
• Spanning trees with many leaves

Cites work

• An Optimal Synchronizer for the Hypercube
• Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• P-Components and the Homogeneous Decomposition of Graphs
• Tree \(t\)-spanners of a graph: minimizing maximum distances efficiently
• Tree Spanners

Cited in

(8)

• Minimum \(t\)-spanners on subcubic graphs
• Hardness and efficiency on \(t\)-admissibility for graph operations
• scientific article; zbMATH DE number 434687 (Why is no real title available?)
• Tree 3-spanners on generalized prisms of graphs
• Polynomial algorithms for sparse spanners on subcubic graphs
• Minimizing distances between vertices and edges through tree t-spanners
• Minimizing distances between vertices and edges through tree \(t\)-spanners
• Tree t-spanners for edge adjacency distances

This page was built for publication: Edge tree spanners

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