Computing the Bandwidth of Interval Graphs
From MaRDI portal
Publication:3483315
DOI10.1137/0403033zbMATH Open0704.05044DBLPjournals/siamdm/KleitmanV90OpenAlexW2040267948WikidataQ100884414 ScholiaQ100884414MaRDI QIDQ3483315FDOQ3483315
Authors: 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
Recommendations
Cited In (38)
- An exponential time 2-approximation algorithm for bandwidth
- Hardness and approximation of minimum distortion embeddings
- Bandwidth on AT-free graphs
- Hardness results for approximating the bandwidth
- Faster Exact Bandwidth
- Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
- Approximating bandwidth by mixing layouts of interval graphs
- An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
- Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
- Bandwidth of bipartite permutation graphs in polynomial time
- Simple linear time recognition of unit interval graphs
- Approximability of the path-distance-width for AT-free graphs
- Subgraph isomorphism in graph classes
- Approximating the bandwidth via volume respecting embeddings
- The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete
- Approximating the bandwidth for asteroidal triple-free graphs
- Title not available (Why is that?)
- Bandwidth of convex bipartite graphs and related graphs
- Title not available (Why is that?)
- Bandwidth of chain graphs
- Tractabilities and intractabilities on geometric intersection graphs
- Approximating the path-distance-width for AT-free graphs and graphs in related classes
- On Harpers' Result Concerning the Bandwidths of Graphs
- Discovering bands from graphs
- Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
- Maximizing the strong triadic closure in split graphs and proper interval graphs
- Finding the minimum bandwidth of an interval graph
- Bandwidth of theta graphs with short paths
- Bandwidth and density for block graphs
- Mixed search number and linear-width of interval and split graphs
- Bandwidth of Bipartite Permutation Graphs in Polynomial Time
- Degree bounds for linear discrepancy of interval orders and disconnected posets
- Title not available (Why is that?)
- Computing \(k\)-atomicity in polynomial time
- Maximizing the strong triadic closure in split graphs and proper interval graphs
- Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
- Mixed Search Number and Linear-Width of Interval and Split Graphs
- Line-distortion, bandwidth and path-length of a graph
This page was built for publication: Computing the Bandwidth of Interval Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3483315)
