Computing the Bandwidth of Interval Graphs

DOI10.1137/0403033zbMath0704.05044WikidataQ100884414 ScholiaQ100884414MaRDI QIDQ3483315

Rakesh V. Vohra, Daniel J. Kleitman

Publication date: 1990

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

Full work available at URL: http://purl.umn.edu/4850

zbMATH Keywords

algorithm; bandwidth; interval graphs

Mathematics Subject Classification ID

05C99: Graph theory

Related Items

Computing $k$-Atomicity in Polynomial Time, Unnamed Item, Faster Exact Bandwidth, Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs, Bandwidth of Bipartite Permutation Graphs in Polynomial Time, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, Approximating the bandwidth for asteroidal triple-free graphs, Bandwidth of chain graphs, An exponential time 2-approximation algorithm for bandwidth, Bandwidth of convex bipartite graphs and related graphs, Subgraph isomorphism in graph classes, Line-distortion, bandwidth and path-length of a graph, Hardness results for approximating the bandwidth, Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs, Bandwidth on AT-free graphs, Simple linear time recognition of unit interval graphs, Degree bounds for linear discrepancy of interval orders and disconnected posets, Hardness and approximation of minimum distortion embeddings, Bandwidth of bipartite permutation graphs in polynomial time, Bandwidth of theta graphs with short paths, Approximating the bandwidth via volume respecting embeddings, Bandwidth and density for block graphs, Tractabilities and intractabilities on geometric intersection graphs, The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete, Maximizing the strong triadic closure in split graphs and proper interval graphs, Approximating the path-distance-width for AT-free graphs and graphs in related classes, Unnamed Item, Mixed search number and linear-width of interval and split graphs, Approximability of the Path-Distance-Width for AT-free Graphs, On Harpers' Result Concerning the Bandwidths of Graphs, Mixed Search Number and Linear-Width of Interval and Split Graphs, Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs