Treewidth in non-ground answer set solving and alliance problems in graphs

DOI10.4230/OASICS.ICLP.2017.12MaRDI QIDQ5240230zbMATH OpenOpenAlexFDO

Authors Bernhard Bliem

Publication date 24 October 2019

Full work available at URL http://drops.dagstuhl.de/opus/volltexte/2018/8465/pdf/OASIcs-ICLP-2017-12.pdf/

zbMATH Keywords

answer set programmingdefensive allianceparameterized complexitysecure settreewidth

Mathematics Subject Classification ID

Logic programming (68N17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The impact of treewidth on grounding and solving of answer set programs
• Answer set solving with bounded treewidth revisited
• ASP programs with groundings of small treewidth
• Treewidth and counting projected answer sets
• Clique-width and directed width measures for answer-set programming

Cites work

• A dynamic-programming based ASP-solver
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A survey on alliances and related parameters in graphs
• Advances in WASP
• All structured programs have small tree width and good register allocation
• Answer set solving with bounded treewidth revisited
• ASP-Core-2 input language format
• Backdoors to tractable answer set programming
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Bucket elimination: A unifying framework for reasoning
• Complexity of secure sets
• Conflict-Driven Answer Set Enumeration
• Conflict-driven answer set solving: from theory to practice
• D-FLAT^2: subset minimization in dynamic programming on tree decompositions made easy
• Easy problems for tree-decomposable graphs
• Extending and implementing the stable model semantics
• Fast Counting with Bounded Treewidth
• Finding a chain graph in a bipartite permutation graph
• Global defensive alliances in graphs
• Graph minors. III. Planar tree-width
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 6843424 (Why is no real title available?)
• scientific article; zbMATH DE number 1368933 (Why is no real title available?)
• scientific article; zbMATH DE number 2104820 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Narrowness, pathwidth, and their application in natural language processing
• On the computational cost of disjunctive logic programming: Propositional case
• Parameterized algorithms
• Parametrized complexity theory.
• Progress in clasp series 3
• Rooted secure sets of trees
• Security in graphs
• The DLV system for knowledge representation and reasoning
• The impact of treewidth on grounding and solving of answer set programs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Towards fixed-parameter tractable algorithms for abstract argumentation
• Tractable answer-set programming with weight constraints: bounded treewidth is not enough

Cited in

(4)

• Answer set solving with bounded treewidth revisited
• Computing secure sets in graphs using answer set programming
• Clique-width and directed width measures for answer-set programming
• The impact of treewidth on grounding and solving of answer set programs

Describes a project that uses

Uses Software

• WASP
• DLV
• clasp

This page was built for publication: Treewidth in non-ground answer set solving and alliance problems in graphs

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