Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
From MaRDI portal
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)
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
Cited in
(52)- Integral mixed unit interval graphs
- Intervalizing \(k\)-colored graphs
- On the thinness of trees
- Bandwidth on AT-free graphs
- scientific article; zbMATH DE number 2230229 (Why is no real title available?)
- Satisfiability problems on intervals and unit intervals
- Minimal proper interval completions
- Bandwidth and pathwidth of three-dimensional grids
- Minimal classes of graphs of unbounded clique-width
- The graph sandwich problem for P₄-sparse graphs
- Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
- On Physical Mapping and the consecutive ones property for sparse matrices
- On intervalizing \(k\)-colored graphs for DNA physical mapping
- 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
- The external constraint 4 nonempty part sandwich problem
- Random Generation and Enumeration of Proper Interval Graphs
- A lower bound for the vertex boundary-width of complete \(k\)-ary trees
- 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
- Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
- On the thinness and proper thinness of a graph
- Small Point-Sets Supporting Graph Stories
- Parameterized problems complete for nondeterministic FPT time and logarithmic space
- 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
- Complexity of rainbow vertex connectivity problems for restricted graph classes
- Canonical antichains of unit interval and bipartite permutation graphs
- Exploring the subexponential complexity of completion problems
- Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- Unit interval graphs: a story with open ends
- Discrete isoperimetric method for bandwidth, pathwidth and treewidth of hypercubes
- A CHARACTERIZATION OF k-TH POWERS Pn,k OF PATHS IN TERMS OF k-TREES
- Distributed interactive proofs for the recognition of some geometric intersection graph classes
- Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
- Unit interval graphs of open and closed intervals
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)
