Bandwidth of Bipartite Permutation Graphs in Polynomial Time

DOI10.1007/978-3-540-78773-0_19MaRDI QIDQ5458530zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

Recommendations

• Bandwidth of bipartite permutation graphs in polynomial time
• Bandwidth of Bipartite Permutation Graphs
• Computing the cutwidth of bipartite permutation graphs in linear time
• scientific article; zbMATH DE number 1696538
• Computing the cutwidth of bipartite permutation graphs in linear time

Cites work

• scientific article; zbMATH DE number 3816913 (Why is no real title available?)
• scientific article; zbMATH DE number 1186230 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 1775392 (Why is no real title available?)
• scientific article; zbMATH DE number 1445378 (Why is no real title available?)
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Bandwidth of Bipartite Permutation Graphs in Polynomial Time
• Bandwidth of chain graphs
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Bipartite permutation graphs
• Computing the Bandwidth of Interval Graphs
• Linear discrepancy and bandwidth
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• The NP-completeness of the bandwidth minimization problem

Cited in

(11)

• Bandwidth of Bipartite Permutation Graphs
• Bandwidth of convex bipartite graphs and related graphs
• scientific article; zbMATH DE number 1696538 (Why is no real title available?)
• Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
• Computing the cutwidth of bipartite permutation graphs in linear time
• Bandwidth of convex bipartite graphs and related graphs
• Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
• Bandwidth of bipartite permutation graphs in polynomial time
• Computing the cutwidth of bipartite permutation graphs in linear time
• Bandwidth of Bipartite Permutation Graphs in Polynomial Time
• A note on maximum differential coloring of planar 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)