An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
From MaRDI portal
Publication:4296515
DOI10.1137/S0895480192232333zbMath0797.05070MaRDI QIDQ4296515
Publication date: 10 October 1994
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
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
