Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs

DOI10.1007/978-3-540-69903-3_30MaRDI QIDQ3512470zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Daniel Meister, Andrzej Proskurowski

Publication date 15 July 2008

Published in Algorithm Theory – SWAT 2008 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69903-3_30

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
• Hardness and approximation of minimum distortion embeddings
• Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
• An exact algorithm for minimum distortion embedding
• An exact algorithm for minimum distortion embedding

Cites work

• Algorithmic graph theory and perfect graphs
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Bandwidth of Bipartite Permutation Graphs in Polynomial Time
• Bipartite permutation graphs
• Computing the Bandwidth of Interval Graphs
• Graph Classes: A Survey
• Low distortion maps between point sets
• Low-distortion embeddings of general metrics into the line
• Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• The complexity of low-distortion embeddings between point sets
• Threshold graphs and related topics

Cited in

(6)

• Hardness and approximation of minimum distortion embeddings
• Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
• 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: Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3512470)