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

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (4)

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

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

This page was built for publication: The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete