Line-distortion, bandwidth and path-length of a graph
From MaRDI portal
Publication:521805
DOI10.1007/s00453-015-0094-7zbMath1359.05120arXiv1409.8389OpenAlexW1608829409MaRDI 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
AT-free graphsapproximation algorithmsminimum bandwidthminimum line-distortionpath-lengthRobertson-Seymour's path-decomposition
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (6)
On the minimum eccentricity shortest path problem ⋮ Equivalence between pathbreadth and strong pathbreadth ⋮ The diameter of AT‐free graphs ⋮ Pathlength of outerplanar graphs ⋮ On Strong Tree-Breadth ⋮ Path eccentricity of graphs
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
This page was built for publication: Line-distortion, bandwidth and path-length of a graph
