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

DOI10.1007/978-3-540-69903-3_30zbMath1155.68557OpenAlexW1548245245MaRDI QIDQ3512470

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

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

Related Items (2)

Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs ⋮ Hardness and approximation of minimum distortion embeddings

Cites Work

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

This page was built for publication: Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs