Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
From MaRDI portal
Publication:4887017
DOI10.1137/S0097539793258143zbMath0852.68072WikidataQ57424547 ScholiaQ57424547MaRDI QIDQ4887017
Publication date: 11 December 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
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, A CHARACTERIZATION OF k-TH POWERS Pn,k OF PATHS IN TERMS OF k-TREES, Unnamed Item, 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, 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, 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, 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
