Revisiting the complexity of and/or graph solution

DOI10.1016/j.jcss.2013.04.001zbMath1311.68078arXiv1203.3249OpenAlexW2027224637MaRDI QIDQ394337

Maise Dantas da Silva, Uéverton dos Santos Souza, Fábio Protti

Publication date: 27 January 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.3249

zbMATH Keywords

computational complexityfixed parameter tractabilityNP-hardnessW[1-hardness]and/or graphsW[2-hardness]

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items

And/or-convexity: a graph convexity based on processes and deadlock models ⋮ Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case ⋮ Tractability, hardness, and kernelization lower bound for and/or graph solution ⋮ Computing the best-case energy complexity of satisfying assignments in monotone circuits ⋮ Succinct certification of monotone circuits ⋮ Succinct monotone circuit certification: planarity and parameterized complexity ⋮ On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem

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
• Models for parallel and distributed computation. Theory, algorithmic techniques and application
• Parametrized complexity theory.
• Computationally Related Problems
• On the Optimal Solutions to AND/OR Series-Parallel Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item