Bandwidth of Bipartite Permutation Graphs in Polynomial Time

DOI10.1007/978-3-540-78773-0_19zbMATH Open1136.05323OpenAlexW1598104667MaRDI QIDQ5458530FDOQ5458530

Authors: Pinar Heggernes, Dieter Kratsch, Daniel Meister 

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_19

Recommendations

• Bandwidth of bipartite permutation graphs in polynomial time
• Bandwidth of Bipartite Permutation Graphs
• Computing the cutwidth of bipartite permutation graphs in linear time
• Publication:2766686
• Computing the cutwidth of bipartite permutation graphs in linear time

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Title not available (Why is that?)
• Bipartite permutation graphs
• The NP-completeness of the bandwidth minimization problem
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Bandwidth of chain graphs
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Title not available (Why is that?)
• Linear discrepancy and bandwidth
• Bandwidth of Bipartite Permutation Graphs in Polynomial Time
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• Title not available (Why is that?)

Cited In (9)

• Bandwidth of convex bipartite graphs and related graphs
• Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
• Bandwidth of bipartite permutation graphs in polynomial time
• Title not available (Why is that?)
• A note on maximum differential coloring of planar graphs
• Bandwidth of Bipartite Permutation Graphs in Polynomial Time
• Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
• Computing the cutwidth of bipartite permutation graphs in linear time
• Bandwidth of Bipartite Permutation Graphs

This page was built for publication: Bandwidth of Bipartite Permutation Graphs in Polynomial Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458530)