Nondeterminism within $P^ * $

DOI10.1137/0222038zbMath0773.68031OpenAlexW1973852671WikidataQ60016242 ScholiaQ60016242MaRDI QIDQ4202212

Jonathan F. Buss, Judy Goldsmith

Publication date: 1 September 1993

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

Full work available at URL: https://doi.org/10.1137/0222038

zbMATH Keywords

nondeterminismquasilinear time

Mathematics Subject Classification ID

Related Items (66)

Parameterized enumeration, transversals, and imperfect phylogeny reconstruction ⋮ Solving large FPT problems on coarse-grained parallel machines ⋮ On the existence of subexponential parameterized algorithms ⋮ Compactors for parameterized counting problems ⋮ Safe Approximation and Its Relation to Kernelization ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ Multistage graph problems on a global budget ⋮ An improved fixed-parameter algorithm for vertex cover ⋮ Refined memorization for vertex cover ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues] ⋮ The Impact of Parameterized Complexity to Interdisciplinary Problem Solving ⋮ On fixed-parameter tractability and approximability of NP optimization problems ⋮ Component order connectivity in directed graphs ⋮ A multivariate framework for weighted FPT algorithms ⋮ Parameterized analysis and crossing minimization problems ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ On log-time alternating Turing machines of alternation depth k ⋮ A parameterized approximation scheme for generalized partial vertex cover ⋮ A polytime preprocess algorithm for the maximum independent set problem ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Multicut in trees viewed through the eyes of vertex cover ⋮ Lower bounds on kernelization ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ Confronting intractability via parameters ⋮ Efficient algorithms for counting parameterized list \(H\)-colorings ⋮ Unnamed Item ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ On directed covering and domination problems ⋮ On quasilinear-time complexity theory ⋮ Fixed-parameter tractability and completeness II: On completeness for W[1] ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ Advice classes of parametrized tractability ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ Parameterized complexity of coloring problems: treewidth versus vertex cover ⋮ A problem reduction based approach to discrete optimization algorithm design ⋮ Improved upper bounds for vertex cover ⋮ Component order connectivity in directed graphs ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover ⋮ The parameterized complexity of editing graphs for bounded degeneracy ⋮ A kernelization algorithm for \(d\)-hitting set ⋮ Linear kernelizations for restricted 3-Hitting Set problems ⋮ Extended formulations for vertex cover ⋮ Approximation in (Poly-) logarithmic space ⋮ Sliding window temporal graph coloring ⋮ Approximation in (Poly-) Logarithmic Space ⋮ Molecular computing, bounded nondeterminism, and efficient recursion ⋮ On width measures and topological problems on semi-complete digraphs ⋮ On parameterized exponential time complexity ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ Dynamic kernels for hitting sets and set packing ⋮ Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover ⋮ The inapproximability of non-NP-hard optimization problems. ⋮ On the complexity of database queries ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ On sparsification for computing treewidth ⋮ On the space and circuit complexity of parameterized problems: classes and completeness ⋮ On Directed Covering and Domination Problems

This page was built for publication: Nondeterminism within $P^ * $