Bandwidth of bipartite permutation graphs in polynomial time

DOI10.1016/j.jda.2008.11.001zbMath1209.05242OpenAlexW2023657479MaRDI QIDQ1044045

Daniel Meister, Pinar Heggernes, Dieter Kratsch

Publication date: 10 December 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.11.001

zbMATH Keywords

bandwidthpolynomial-time algorithmNP-complete problembipartite permutation graphsgraph layout problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Linear-time algorithms for counting independent sets in bipartite permutation graphs ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Permutation bigraphs and interval containments ⋮ Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs ⋮ Bandwidth of convex bipartite graphs and related graphs ⋮ Subgraph isomorphism in graph classes ⋮ Bandwidth on AT-free graphs ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Line-distortion, bandwidth and path-length of a graph

Uses Software

• symrcm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bandwidth of chain graphs
• Bipartite permutation graphs
• The NP-completeness of the bandwidth minimization problem
• Linear discrepancy and bandwidth
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Beyond NP-completeness for problems of bounded width (extended abstract)
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Computing the Bandwidth of Interval Graphs
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Graph Classes: A Survey
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• On Exact Algorithms for Treewidth
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques