Finding the minimum bandwidth of an interval graph
From MaRDI portal
Publication:1090458
DOI10.1016/0890-5401(87)90028-9zbMath0621.68042OpenAlexW1992988744MaRDI QIDQ1090458
Publication date: 1987
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(87)90028-9
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (7)
The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete ⋮ Parameterized complexity of multicut in weighted trees ⋮ On finding the minimum bandwidth of interval graphs ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ An improved simulated annealing algorithm for bandwidth minimization ⋮ Bandwidth of theta graphs with short paths ⋮ Achromatic number is NP-complete for cographs and interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Characterizations of strongly chordal graphs
- Finding Hamiltonian circuits in interval graphs
- A recognition algorithm for the intersection graphs of directed paths in directed trees
- The NP-completeness of the bandwidth minimization problem
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- Representation of a finite graph by a set of intervals on the real line
- The NP-completeness column: an ongoing guide
- 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 Characterization of Comparability Graphs and of Interval Graphs
- Total domination in interval graphs
This page was built for publication: Finding the minimum bandwidth of an interval graph
