Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
DOI10.1137/S0097539793258143zbMATH Open0852.68072WikidataQ57424547 ScholiaQ57424547MaRDI QIDQ4887017FDOQ4887017
Authors: Haim Kaplan, Ron Shamir 
Publication date: 11 December 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
- Polynomial kernels for proper interval completion and related problems
- Polynomial kernels for proper interval completion and related problems
- From Tree-Width to Clique-Width: Excluding a Unit Interval Graph
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- The interval graph completion problem for the complete multipartite graphs
Computing methodologies and applications (68U99) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (52)
- Parameterized problems complete for nondeterministic FPT time and logarithmic space
- Discrete isoperimetric method for bandwidth, pathwidth and treewidth of hypercubes
- On the thinness of trees
- Title not available (Why is that?)
- Bandwidth on AT-free graphs
- Satisfiability problems on intervals and unit intervals
- Minimal proper interval completions
- Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
- Bandwidth and pathwidth of three-dimensional grids
- On Physical Mapping and the consecutive ones property for sparse matrices
- On intervalizing \(k\)-colored graphs for DNA physical mapping
- Minimal classes of graphs of unbounded clique-width
- The graph sandwich problem for \(P_4\)-sparse graphs
- Further hardness results on rainbow and strong rainbow connectivity
- Matrix sandwich problems
- Approximability of the path-distance-width for AT-free graphs
- Embeddings of \(k\)-connected graphs of pathwidth \(k\)
- The graph sandwich problem for 1-join composition is NP-complete
- A partial k-arboretum of graphs with bounded treewidth
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- Bandwidth of chain graphs
- On decision and optimization (\(k\),\(l\))-graph sandwich problems
- Tractabilities and intractabilities on geometric intersection graphs
- Random Generation and Enumeration of Proper Interval Graphs
- The external constraint 4 nonempty part sandwich problem
- A lower bound for the vertex boundary-width of complete \(k\)-ary trees
- Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
- Approximating the path-distance-width for AT-free graphs and graphs in related classes
- Some approximation algorithms for the clique partition problem in weighted interval graphs
- On the thinness and proper thinness of a graph
- Small Point-Sets Supporting Graph Stories
- Small point-sets supporting graph stories
- The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
- Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
- U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- Mixed unit interval graphs
- \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- On the proper intervalization of colored caterpillar trees
- The Proper Interval Colored Graph problem for caterpillar trees
- Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs
- Exploring the subexponential complexity of completion problems
- Complexity of rainbow vertex connectivity problems for restricted graph classes
- Canonical antichains of unit interval and bipartite permutation graphs
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- Unit interval graphs: a story with open ends
- A CHARACTERIZATION OF k-TH POWERS Pn,k OF PATHS IN TERMS OF k-TREES
- Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
- Unit interval graphs of open and closed intervals
- Distributed interactive proofs for the recognition of some geometric intersection graph classes
- Intervalizing \(k\)-colored graphs
- Integral mixed unit interval graphs
This page was built for publication: Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4887017)
