On finding the minimum bandwidth of interval graphs

DOI10.1016/0890-5401(91)90045-4zbMath0738.68046OpenAlexW2055217195MaRDI QIDQ1183610

R. Mahesh, Aravind Srinivasan, C. Pandu Rangan

Publication date: 28 June 1992

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(91)90045-4

zbMATH Keywords

bandwidthinterval graphlayout of an undirected graph

Mathematics Subject Classification ID

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

Related Items (13)

The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Graph layout problems ⋮ Hardness results for approximating the bandwidth ⋮ Approximating the bandwidth for asteroidal triple-free graphs ⋮ Approximating the path-distance-width for AT-free graphs and graphs in related classes ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Generalized vertex covering in interval graphs ⋮ Bandwidth and topological bandwidth of graphs with few \(P_4\)'s ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ Bounds on mincut for Cayley graphs over Abelian groups ⋮ Approximability of the Path-Distance-Width for AT-free Graphs ⋮ Interval-Valued Degrees of Belief: Applications of Interval Computations to Expert Systems and Intelligent Control

Cites Work

• Unnamed Item
• Finding Hamiltonian circuits in interval graphs
• Finding the minimum bandwidth of an interval graph
• A unified approach to domination problems on interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Linear algorithm for domatic number problem on interval graphs

This page was built for publication: On finding the minimum bandwidth of interval graphs