Finding the minimum bandwidth of an interval graph
An assignment of unique integers to the vertices of a graph is called a linear layout. The bandwidth minimization problem (BANDWIDTH) is the following: Given a graph \(G=(V,E)\) and an integer k, determine whether there exists a linear layout of G such that the maximum difference between adjacent vertices is bounded by k. Interval graphs are the intersection graphs of a family of intervals of the real line. BANDWIDTH remains NP-complete even when restricted to special subclasses of trees. We show that BANDWIDTH can be solved in time \(O(n^ 2)\) for interval graphs. Moreover, for a given interval graph a linear layout with minimum bandwidth can be constructed in time \(O(n^ 2\log n)\). As a by-product we get that this construction can be done for proper interval graphs in time O(n log n\(+m)\).
- A Characterization of Comparability Graphs and of Interval Graphs
- A recognition algorithm for the intersection graphs of directed paths in directed trees
- Characterizations of strongly chordal graphs
- Complexity Results for Bandwidth Minimization
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Finding Hamiltonian circuits in interval graphs
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3908482 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 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
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2
- The NP-completeness column: an ongoing guide
- The NP-completeness of the bandwidth minimization problem
- Total domination in interval graphs
- On finding the minimum bandwidth of interval graphs
- Bandwidth of theta graphs with short paths
- Interval degree and bandwidth of a graph
- Tractabilities and intractabilities on geometric intersection graphs
- A simple linear-time algorithm for the recognition of bandwidth-2 biconnected graphs
- Achromatic number is NP-complete for cographs and interval graphs
- The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete
- An improved simulated annealing algorithm for bandwidth minimization
- Profile minimization on products of graphs
- Laying out sparse graphs with provably minimum bandwidth
- On Some Variants of the Bandwidth Minimization Problem
- Computing the Bandwidth of Interval Graphs
- scientific article; zbMATH DE number 3974992 (Why is no real title available?)
- scientific article; zbMATH DE number 4075107 (Why is no real title available?)
- scientific article; zbMATH DE number 1304325 (Why is no real title available?)
- An O( n \log n ) Algorithm for Bandwidth of Interval Graphs
- Parameterized complexity of multicut in weighted trees
- Domination and Cut Problems on Chordal Graphs with Bounded Leafage
- Domination and cut problems on chordal graphs with bounded leafage
- Discovering bands from graphs
This page was built for publication: Finding the minimum bandwidth of an interval graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1090458)
