An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs

DOI10.1137/S0895480192232333zbMath0797.05070MaRDI QIDQ4296515

Alan P. Sprague

Publication date: 10 October 1994

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

algorithmbandwidthinterval graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (21)

The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete ⋮ Bandwidth of chain graphs ⋮ Graph bandwidth of weighted caterpillars ⋮ Restrictions of minimum spanner problems ⋮ Unnamed Item ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Hardness results for approximating the bandwidth ⋮ Approximating the bandwidth for asteroidal triple-free graphs ⋮ Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs ⋮ Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs ⋮ Bandwidth of convex bipartite graphs and related graphs ⋮ Approximating the path-distance-width for AT-free graphs and graphs in related classes ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Bandwidth and topological bandwidth of graphs with few \(P_4\)'s ⋮ Hardness and approximation of minimum distortion embeddings ⋮ Approximability of the Path-Distance-Width for AT-free Graphs ⋮ Bandwidth of bipartite permutation graphs in polynomial time ⋮ Bandwidth and density for block graphs

This page was built for publication: An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs