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

DOI10.1007/978-3-540-69903-3_30zbMATH Open1155.68557OpenAlexW1548245245MaRDI QIDQ3512470FDOQ3512470

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

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

Mathematics Subject Classification ID

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

Cites Work

• Graph Classes: A Survey
• Algorithmic graph theory and perfect graphs
• Threshold graphs and related topics
• 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
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Low-distortion embeddings of general metrics into the line
• Bandwidth of Bipartite Permutation Graphs in Polynomial Time
• Low distortion maps between point sets
• Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs

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)