Tractability, hardness, and kernelization lower bound for and/or graph solution

DOI10.1016/J.DAM.2017.07.029MaRDI QIDQ2410230zbMATH OpenOpenAlexFDO

Authors Uéverton dos Santos Souza, Fábio Protti

Publication date 17 October 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2017.07.029

zbMATH Keywords

and/or graphsclique-widthFPTtree-widthW[1-hard]W[P-complete]

Mathematics Subject Classification ID

Graph theory (05C99) Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Revisiting the complexity of and/or graph solution
• scientific article; zbMATH DE number 2089979
• Searching for a minimal solution subgraph in explicit AND/OR graphs
• scientific article; zbMATH DE number 5044336
• scientific article; zbMATH DE number 1163292

Cites work

• A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem
• A randomized competitive algorithm for evaluating priced AND/OR trees
• Computationally Related Problems
• Directed hypergraphs and applications
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Graph structure and monadic second-order logic. A language-theoretic approach
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 2050889 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• Kernel bounds for path and cycle problems
• Kernelization: new upper and lower bound techniques
• Lower bounds on kernelization
• Models for parallel and distributed computation. Theory, algorithmic techniques and application
• New graph classes of bounded clique-width
• On problems without polynomial kernels
• On the model-checking of monadic second-order formulas with edge set quantifications
• On the Optimal Solutions to AND/OR Series-Parallel Graphs
• On the parameterized complexity of multiple-interval graph problems
• Revisiting the complexity of and/or graph solution

Cited in

(7)

• Succinct monotone circuit certification: planarity and parameterized complexity
• On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
• Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case
• Succinct certification of monotone circuits
• Computing the best-case energy complexity of satisfying assignments in monotone circuits
• Revisiting the complexity of and/or graph solution
• scientific article; zbMATH DE number 2089979 (Why is no real title available?)

This page was built for publication: Tractability, hardness, and kernelization lower bound for and/or graph solution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2410230)