Computing the Bandwidth of Interval Graphs
From MaRDI portal
Publication:3483315
DOI10.1137/0403033zbMath0704.05044WikidataQ100884414 ScholiaQ100884414MaRDI QIDQ3483315
Daniel J. Kleitman, Rakesh V. Vohra
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
05C99: Graph theory
Related Items
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, 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, The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete, 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
