Collective additive tree spanners for circle graphs and polygonal graphs

DOI10.1016/J.DAM.2012.03.036MaRDI QIDQ444436zbMATH OpenOpenAlexFDO

Authors Feodor F. Dragan, Ekkehard Köhler, Derek G. Corneil, Yang Xiang

Publication date 14 August 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.03.036

zbMATH Keywords

graph algorithmsbalanced separatorscircle graphscollective additive tree spannerspolygonal graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Additive Spanners for Circle Graphs and Polygonal Graphs
• Algorithm Theory - SWAT 2004
• Collective tree spanners in graphs with bounded parameters
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• Collective tree spanners of graphs

Cites work

• scientific article; zbMATH DE number 53860 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• scientific article; zbMATH DE number 3448387 (Why is no real title available?)
• A tight bound on approximating arbitrary metrics by tree metrics
• Additive Spanners for Circle Graphs and Polygonal Graphs
• Additive Tree Spanners
• Additive graph spanners
• Additive sparse spanners for graphs with bounded length of largest induced cycle
• Algorithmic graph theory and perfect graphs
• Algorithms and Computation
• An Optimal Synchronizer for the Hypercube
• Collective Tree Spanners and Routing in AT-free Related Graphs
• Collective tree spanners of graphs
• Distance approximating spanning trees
• Distributed Computing: A Locality-Sensitive Approach
• Graph spanners
• Graph-Theoretic Concepts in Computer Science
• Polygon Graph Recognition
• Proximity-preserving labeling schemes
• Recognition of Circle Graphs
• There are planar graphs almost as good as the complete graph
• Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
• Tree Spanners

Cited in

(12)

• Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \)
• On polygon numbers of circle graphs and distance hereditary graphs
• Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences
• How to use spanning trees to navigate in graphs
• Graph-Theoretic Concepts in Computer Science
• Algorithm Theory - SWAT 2004
• Clifford algebra and the discretizable molecular distance geometry problem
• Additive graph spanners
• Collective Additive Tree Spanners of Homogeneously Orderable Graphs
• Additive Spanners for Circle Graphs and Polygonal Graphs
• Collective tree spanners for unit disk graphs with applications
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences

This page was built for publication: Collective additive tree spanners for circle graphs and polygonal graphs

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