Bandwidth of convex bipartite graphs and related graphs

DOI10.1016/j.ipl.2012.02.012zbMath1243.68327MaRDI 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 graphs; 2-directional orthogonal ray graphs; bandwidth problem

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

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

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