Tree t-spanners in outerplanar graphs via supply demand partition

DOI10.1016/J.DAM.2014.11.001MaRDI QIDQ496441zbMATH OpenOpenAlexFDO

Authors N. S. Narayanaswamy, G. Ramakrishna

Publication date 21 September 2015

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

Full work available at URL https://arxiv.org/abs/1210.7919

zbMATH Keywords

outerplanar graphsminimum stretch spanning treesupply-demand tree partitiontree \(t\)-spanner

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A tree t-spanner of an unweighted graph G is a spanning tree T such that for every two vertices their distance in T is at most t times their distance in G. Given an unweighted graph G and a positive integer t as input, the tree t-spanner problem is to compute a tree t-spanner of G if one exists. This decision problem is known to be NP-complete even in the restricted class of unweighted planar graphs. We present a linear-time reduction from tree t-spanner in outerplanar graphs to the supply-demand tree partition problem. Based on this reduction, we obtain a linear-time algorithm to solve tree t-spanner in outerplanar graphs. Consequently, we show that the minimum value of t for which an input outerplanar graph on n vertices has a tree t-spanner can be found in O(n log n) time.

Recommendations

• scientific article; zbMATH DE number 1262806
• Spanners in sparse graphs
• Tree spanners in planar graphs
• Tree Spanners
• scientific article; zbMATH DE number 1979496

Cites work

• scientific article; zbMATH DE number 1979534 (Why is no real title available?)
• A Practical Approach to Courcelle's Theorem
• Additive Tree Spanners
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation of pathwidth of outerplanar graphs
• Characterizations of outerplanar graphs
• Distributed Computing: A Locality-Sensitive Approach
• On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
• Reconstructing the shape of a tree from observed dissimilarity data
• Spanners in sparse graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Tree 3-spanners on interval, permutation and regular bipartite graphs
• Tree Spanners
• Tree spanners for bipartite graphs and probe interval graphs
• Tree spanners in planar graphs
• Tree spanners on chordal graphs: complexity and algorithms

Cited in

(6)

• Parameterized Minimum Cost Partition of a Tree with Supply and Demand
• Tree spanners of bounded degree graphs
• A heuristic method for solving the problem of partitioning graphs with supply and demand
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• A mixed integer program for partitioning graphs with supply and demand emphasizing sparse graphs
• Partition on trees with supply and demand: kernelization and algorithms

This page was built for publication: Tree \(t\)-spanners in outerplanar graphs via supply demand partition

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