Tree t-spanners in outerplanar graphs via supply demand partition

DOI10.1016/J.DAM.2014.11.001zbMATH Open1320.05027arXiv1210.7919OpenAlexW2964285712MaRDI QIDQ496441FDOQ496441

Authors: N. S. Narayanaswamy, G. Ramakrishna 

Publication date: 21 September 2015

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

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.

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

Recommendations

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

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)

Cites Work

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

Cited In (6)

• 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
• Tree spanners of bounded degree graphs
• Parameterized Minimum Cost Partition of a Tree with Supply and Demand
• Partition on trees with supply and demand: kernelization and algorithms
• A mixed integer program for partitioning graphs with supply and demand emphasizing sparse graphs

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)