Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs

DOI10.1016/j.tcs.2011.01.005zbMath1211.68287MaRDI 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

zbMATH Keywords

distortion; graph algorithms; polynomial-time algorithms; forbidden induced subgraphs characterisation; threshold graphs; bipartite permutation graphs; embedding into a path

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C30: Enumeration in graph theory

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Permutation bigraphs and interval containments, Line-distortion, bandwidth and path-length of a graph, On the minimum eccentricity shortest path problem, On the Minimum Eccentricity Shortest Path Problem

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