Computing the Bandwidth of Interval Graphs
From MaRDI portal
Publication:3483315
DOI10.1137/0403033zbMath0704.05044OpenAlexW2040267948WikidataQ100884414 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
Related Items
The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete, Bandwidth of chain graphs, Faster Exact Bandwidth, Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs, Unnamed Item, An exponential time 2-approximation algorithm for bandwidth, Hardness results for approximating the bandwidth, Approximating the bandwidth for asteroidal triple-free graphs, Mixed Search Number and Linear-Width of Interval and Split Graphs, Maximizing the strong triadic closure in split graphs and proper interval 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, Subgraph isomorphism in graph classes, Bandwidth on AT-free graphs, Tractabilities and intractabilities on geometric intersection graphs, Computing $k$-Atomicity in Polynomial Time, Simple linear time recognition of unit interval graphs, Bandwidth of theta graphs with short paths, Line-distortion, bandwidth and path-length of a graph, Degree bounds for linear discrepancy of interval orders and disconnected posets, Mixed search number and linear-width of interval and split graphs, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, Hardness and approximation of minimum distortion embeddings, On Harpers' Result Concerning the Bandwidths of Graphs, Bandwidth of Bipartite Permutation Graphs in Polynomial Time, Unnamed Item, Approximability of the Path-Distance-Width for AT-free Graphs, Approximating the bandwidth via volume respecting embeddings, Bandwidth of bipartite permutation graphs in polynomial time, Bandwidth and density for block graphs
