Line-distortion, bandwidth and path-length of a graph

DOI10.1007/s00453-015-0094-7zbMath1359.05120arXiv1409.8389MaRDI QIDQ521805

Arne Leitert, Ekkehard Köhler, Feodor F. Dragan

Publication date: 12 April 2017

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

AT-free graphs; approximation algorithms; minimum bandwidth; minimum line-distortion; path-length; Robertson-Seymour's path-decomposition

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

The diameter of AT‐free graphs, Pathlength of outerplanar graphs, Path eccentricity of graphs, On the minimum eccentricity shortest path problem, Equivalence between pathbreadth and strong pathbreadth, On Strong Tree-Breadth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bandwidth of convex bipartite graphs and related graphs
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• An exact algorithm for minimum distortion embedding
• Hardness results for approximating the bandwidth
• Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
• Bandwidth on AT-free graphs
• An optimal greedy heuristic to color interval graphs
• On the complexity of computing treelength
• Hardness and approximation of minimum distortion embeddings
• Bandwidth of bipartite permutation graphs in polynomial time
• Graph minors. I. Excluding a forest
• Comparability graphs and intersection graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Approximating the bandwidth via volume respecting embeddings
• Some properties of invariant sets of a flow
• Tree-decompositions with bags of small diameter
• Incidence matrices and interval graphs
• Improved Bandwidth Approximation for Trees and Chordal Graphs
• Distortion is Fixed Parameter Tractable
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Line-Distortion, Bandwidth and Path-Length of a Graph
• Computing the Bandwidth of Interval Graphs
• Low-distortion embeddings of general metrics into the line
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• On the 2-Chain Subgraph Cover and Related Problems
• Asteroidal Triple-Free Graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Approximating Bandwidth by Mixing Layouts of Interval Graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• A Characterization of Comparability Graphs and of Interval Graphs