Beyond NP-completeness for problems of bounded width (extended abstract)

DOI10.1145/195058.195229zbMath1345.68152WikidataQ59567994 ScholiaQ59567994MaRDI QIDQ2817636

Michael R. Fellows, Hans L. Bodlaender, Michael T. Hallett

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195229

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

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

Related Items

Faster Exact Bandwidth, Bandwidth of Bipartite Permutation Graphs in Polynomial Time, On approximation intractability of the path-distance-width problem, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, On intervalizing \(k\)-colored graphs for DNA physical mapping, An exponential time 2-approximation algorithm for bandwidth, Bandwidth and distortion revisited, Parameterized complexity and approximability of the longest compatible sequence problem, Bandwidth on AT-free graphs, Exact and approximate bandwidth, The complexity ecology of parameters: An illustration using bounded max leaf number, Online promise problems with online width metrics, Bandwidth of bipartite permutation graphs in polynomial time, Parameterized circuit complexity and the \(W\) hierarchy, Threshold dominating sets and an improved characterization of \(W[2\)], On fixed-parameter tractability and approximability of NP optimization problems, The parameterized complexity of sequence alignment and consensus, Characterizations and algorithmic applications of chordal graph embeddings, The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, Approximating the bandwidth via volume respecting embeddings, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling], The complexity of irredundant sets parameterized by size, Parameterized computation and complexity: a new approach dealing with NP-hardness, The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, Graph Minors and Parameterized Algorithm Design, The Proper Interval Colored Graph problem for caterpillar trees, Parameterized Complexity and Approximability of the SLCS Problem, On the proper intervalization of colored caterpillar trees, Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs, An Exponential Time 2-Approximation Algorithm for Bandwidth