Bandwidth of convex bipartite graphs and related graphs

DOI10.1016/j.ipl.2012.02.012zbMath1243.68327OpenAlexW2001287420MaRDI QIDQ436544

Shuichi Ueno, Anish Man Singh Shrestha, Satoshi Tayu

Publication date: 25 July 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2012.02.012

zbMATH Keywords

approximation algorithms(bi)convex bipartite graphs2-directional orthogonal ray graphsbandwidth problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (3)

Compact representation of graphs with bounded bandwidth or treedepth ⋮ On orthogonal ray trees ⋮ Line-distortion, bandwidth and path-length of a graph

Cites Work

• Bandwidth of chain graphs
• On orthogonal ray graphs
• Hardness results for approximating the bandwidth
• Bandwidth of bipartite permutation graphs in polynomial time
• Bipartite permutation graphs
• The NP-completeness of the bandwidth minimization problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Computing the Bandwidth of Interval Graphs
• Bandwidth of Bipartite Permutation Graphs
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Graph Classes: A Survey
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• A remark on a problem of Harary

This page was built for publication: Bandwidth of convex bipartite graphs and related graphs