Collective tree spanners in graphs with bounded parameters
type: Item
instance of: scholarly article
title: Collective tree spanners in graphs with bounded parameters
zbMATH Open document ID: 1223.05247
author: Feodor F. Dragan
author: Chenyu Yan
published in: Algorithmica
publication date: 2010-03-04T00:00:00Z
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 5677425
zbMATH Keywords: Spanners
zbMATH Keywords: Tree spanners
zbMATH Keywords: Graph distance
zbMATH Keywords: Balanced separator
zbMATH Keywords: Graph decomposition
zbMATH Keywords: Tree-width
zbMATH Keywords: Clique-width
zbMATH Keywords: Planar graphs
zbMATH Keywords: \(c\)-Chordal graphs
zbMATH Keywords: Message routing
zbMATH Keywords: Efficient algorithms
MaRDI profile type: Publication
full work available at URL: s00453-008-9194-y
OpenAlex ID: W2016638039
cites work: Distributed Computing
cites work: Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
cites work: SOFSEM 2005: Theory and Practice of Computer Science
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: LexBFS-orderings and powers of chordal graphs
cites work: Tree Spanners
cites work: Q4437500
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Upper bounds to the clique width of graphs
cites work: On the Problem of Partitioning Planar Graphs
cites work: Q3737448
cites work: Algorithms and Computation
cites work: Collective Tree Spanners and Routing in AT-free Related Graphs
cites work: Collective tree spanners of graphs
cites work: Approximating \(k\)-spanner problems for \(k>2\)
cites work: $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
cites work: Q5501267
cites work: Q4535803
cites work: A separator theorem for graphs of bounded genus
cites work: A Separator Theorem for Chordal Graphs
cites work: Q3328583
cites work: Q4944973
cites work: Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
cites work: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
cites work: Treewidth. Computations and approximations
cites work: A Separator Theorem for Planar Graphs
cites work: Additive graph spanners
cites work: Graph spanners
cites work: An Optimal Synchronizer for the Hypercube
cites work: Additive Tree Spanners
cites work: Graph minors. II. Algorithmic aspects of tree-width
DOI: 10.1007/S00453-008-9194-Y
description: scientific article; zbMATH DE number 5677425