Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
From MaRDI portal
Publication:631789
DOI10.1016/j.tcs.2011.01.005zbMath1211.68287OpenAlexW2033622225MaRDI QIDQ631789
Pinar Heggernes, Daniel Meister, Andrzej Proskurowski
Publication date: 14 March 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.01.005
distortiongraph algorithmspolynomial-time algorithmsforbidden induced subgraphs characterisationthreshold graphsbipartite permutation graphsembedding into a path
Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
On the Minimum Eccentricity Shortest Path Problem, On the minimum eccentricity shortest path problem, Permutation bigraphs and interval containments, Line-distortion, bandwidth and path-length of a graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hardness and approximation of minimum distortion embeddings
- Bandwidth of bipartite permutation graphs in polynomial time
- Bipartite permutation graphs
- Linear discrepancy and bandwidth
- Algorithmic graph theory and perfect graphs
- Threshold graphs and related topics
- Optimal greedy algorithms for indifference graphs
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Computing the Bandwidth of Interval Graphs
- Low distortion maps between point sets
- Low-distortion embeddings of general metrics into the line
- Distortion Is Fixed Parameter Tractable
- Graph Classes: A Survey
- An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs