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

DOI10.1016/J.TCS.2011.01.005MaRDI QIDQ631789zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

graph algorithmsforbidden induced subgraphs characterisationdistortionpolynomial-time algorithmsthreshold graphsbipartite permutation graphsembedding into a path

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30)

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

Cites work

• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Approximation algorithms for embedding general metrics into trees
• 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
• Distortion Is Fixed Parameter Tractable
• Graph Classes: A Survey
• Hardness and approximation of minimum distortion embeddings
• Linear discrepancy and bandwidth
• Low distortion maps between point sets
• Low-distortion embeddings of general metrics into the line
• Optimal greedy algorithms for indifference 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

(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)