The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete

DOI10.1016/S0304-3975(03)00238-XzbMath1070.68123MaRDI QIDQ1885051

David Muradian

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

Critical elements in combinatorially closed families of graph classes, Exploring the gap between treedepth and vertex cover through vertex integrity, Exploring the gap between treedepth and vertex cover through vertex integrity, Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}

Cites Work

• Unnamed Item
• Finding the minimum bandwidth of an interval graph
• On finding the minimum bandwidth of interval graphs
• The NP-completeness of the bandwidth minimization problem
• Bandwidth and density for block graphs
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Computing the Bandwidth of Interval Graphs
• The bandwidth problem for graphs and matrices—a survey
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Complexity Results for Bandwidth Minimization
• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Optimal numberings and isoperimetric problems on graphs