Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
DOI10.1016/J.TCS.2011.01.005zbMATH Open1211.68287OpenAlexW2033622225MaRDI QIDQ631789FDOQ631789
Authors: 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
Recommendations
- Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
- Hardness and approximation of minimum distortion embeddings
- An exact algorithm for minimum distortion embedding
- Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
- An exact algorithm for minimum distortion embedding
graph algorithmsforbidden induced subgraphs characterisationdistortionpolynomial-time algorithmsthreshold graphsbipartite permutation graphsembedding into a path
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30)
Cites Work
- Graph Classes: A Survey
- Algorithmic graph theory and perfect graphs
- Threshold graphs and related topics
- Optimal greedy algorithms for indifference graphs
- Title not available (Why is that?)
- Bipartite permutation graphs
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Computing the Bandwidth of Interval Graphs
- An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
- The complexity of low-distortion embeddings between point sets
- Bandwidth of bipartite permutation graphs in polynomial time
- Linear discrepancy and bandwidth
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Distortion Is Fixed Parameter Tractable
- Low-distortion embeddings of general metrics into the line
- Approximation algorithms for embedding general metrics into trees
- Hardness and approximation of minimum distortion embeddings
- Low distortion maps between point sets
Cited In (10)
- Hardness and approximation of minimum distortion embeddings
- On the minimum eccentricity shortest path problem
- An exact algorithm for minimum distortion embedding
- An exact algorithm for minimum distortion embedding
- On the minimum eccentricity shortest path problem
- Permutation bigraphs and interval containments
- Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
- Line-distortion, bandwidth and path-length of a graph
- Line-distortion, bandwidth and path-length of a graph
- Using Graphs for the Analysis and Construction of Permutation Distance-Preserving Mappings
This page was built for publication: Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q631789)
