The complexity of node blocking for dags

DOI10.1016/J.JCTA.2010.03.011MaRDI QIDQ616455zbMATH OpenOpenAlexFDO

Authors Dariusz Dereniowski

Publication date 7 January 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcta.2010.03.011

zbMATH Keywords

annihilation gamenode blockingPSPACE-completeness

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Games on graphs (graph-theoretic aspects) (05C57) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43)

Recommendations

• The computational complexity of optimal blocking of vertices in the digraph
• scientific article; zbMATH DE number 1696521
• Node-searching problem on block graphs
• The parallel complexity of finding a blocking flow in a 3-layer network
• Parameterized complexity of DAG partitioning
• A parallel blocking flow algorithm for acyclic networks
• Blocking in parallel multisearch problems
• Blocking for external graph searching
• A digraph theoretic parallelism in block methods

Cites work

• Complexity of problems in games, graphs and algebraic equations
• scientific article; zbMATH DE number 988847 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1944403 (Why is no real title available?)
• scientific article; zbMATH DE number 1834637 (Why is no real title available?)
• Misère annihilation games
• On the complexity of some two-person perfect-information games
• PSPACE-Hardness of some combinatorial games
• The complexity of pursuit on a graph
• Theory of annihilation games
• Theory of annihilation games. I

This page was built for publication: The complexity of node blocking for dags

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