Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques

DOI10.1137/S0097539793258143zbMath0852.68072WikidataQ57424547 ScholiaQ57424547MaRDI QIDQ4887017

Ron Shamir, Haim Kaplan

Publication date: 11 December 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

bandwidthinterval graphsparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies and applications (68U99) Complexity of computation (including implicit computational complexity) (03D15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The graph sandwich problem for 1-join composition is NP-complete ⋮ Bandwidth of chain graphs ⋮ On decision and optimization (\(k\),\(l\))-graph sandwich problems ⋮ Satisfiability problems on intervals and unit intervals ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs ⋮ Small Point-Sets Supporting Graph Stories ⋮ A lower bound for the vertex boundary-width of complete \(k\)-ary trees ⋮ On the thinness of trees ⋮ Small point-sets supporting graph stories ⋮ Further hardness results on rainbow and strong rainbow connectivity ⋮ Integral mixed unit interval graphs ⋮ Approximating the path-distance-width for AT-free graphs and graphs in related classes ⋮ Bandwidth on AT-free graphs ⋮ Canonical antichains of unit interval and bipartite permutation graphs ⋮ Minimal classes of graphs of unbounded clique-width ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Complexity of rainbow vertex connectivity problems for restricted graph classes ⋮ Intervalizing k-colored graphs ⋮ Unit Interval Graphs of Open and Closed Intervals ⋮ The external constraint 4 nonempty part sandwich problem ⋮ Minimal proper interval completions ⋮ Bandwidth and pathwidth of three-dimensional grids ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Embeddings of \(k\)-connected graphs of pathwidth \(k\) ⋮ Unnamed Item ⋮ Mixed unit interval graphs ⋮ The sandwich problem for cutsets: clique cutset, \(k\)-star cutset ⋮ Unnamed Item ⋮ Bandwidth and topological bandwidth of graphs with few \(P_4\)'s ⋮ Random Generation and Enumeration of Proper Interval Graphs ⋮ On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs ⋮ Some approximation algorithms for the clique partition problem in weighted interval graphs ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ On Physical Mapping and the consecutive ones property for sparse matrices ⋮ On intervalizing \(k\)-colored graphs for DNA physical mapping ⋮ Minimum reload cost graph factors ⋮ The graph sandwich problem for \(P_4\)-sparse graphs ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited ⋮ Unnamed Item ⋮ Approximability of the Path-Distance-Width for AT-free Graphs ⋮ On the proper intervalization of colored caterpillar trees ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ A CHARACTERIZATION OF k-TH POWERS P_n,k OF PATHS IN TERMS OF k-TREES ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes ⋮ Matrix sandwich problems ⋮ The Proper Interval Colored Graph problem for caterpillar trees

This page was built for publication: Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques