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

bandwidth; interval graphs; parameterized complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68U99: Computing methodologies and applications

03D15: Complexity of computation (including implicit computational complexity)

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Intervalizing k-colored graphs, Unit Interval Graphs of Open and Closed Intervals, Unnamed Item, A CHARACTERIZATION OF k-TH POWERS P_n,k OF PATHS IN TERMS OF k-TREES, Unnamed Item, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, 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, 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, On the thinness of trees, Small point-sets supporting graph stories, Bandwidth of chain graphs, Complexity of rainbow vertex connectivity problems for restricted graph classes, The external constraint 4 nonempty part sandwich problem, Bandwidth and pathwidth of three-dimensional grids, Bandwidth on AT-free graphs, Canonical antichains of unit interval and bipartite permutation graphs, Minimal classes of graphs of unbounded clique-width, Mixed unit interval graphs, Further hardness results on rainbow and strong rainbow connectivity, Minimal proper interval completions, 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, The graph sandwich problem for \(P_4\)-sparse graphs, A partial k-arboretum of graphs with bounded treewidth, Matrix sandwich problems, Satisfiability problems on intervals and unit intervals, The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, The graph sandwich problem for 1-join composition is NP-complete, Tractabilities and intractabilities on geometric intersection graphs, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Embeddings of \(k\)-connected graphs of pathwidth \(k\), On decision and optimization (\(k\),\(l\))-graph sandwich problems, Integral mixed unit interval graphs, \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited, Distributed interactive proofs for the recognition of some geometric intersection graph classes, 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, The sandwich problem for cutsets: clique cutset, \(k\)-star cutset, Unnamed Item, Exploring the Subexponential Complexity of Completion Problems, Approximability of the Path-Distance-Width for AT-free Graphs, The Proper Interval Colored Graph problem for caterpillar trees, Random Generation and Enumeration of Proper Interval Graphs, On the proper intervalization of colored caterpillar trees