Finding kernels or solving SAT

DOI10.1016/J.JDA.2011.11.004MaRDI QIDQ414435zbMATHOpenAlexFDO

Authors Michał Walicki, Sjur Dyrkolbotn

Publication date 11 May 2012

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2011.11.004

zbMATH Keywords

kerneldigraphssatisfiabilitypropositional logic

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Expressive power of digraph solvability
• Kernels in planar digraphs
• Strong kernel in certain oriented networks
• A Polyhedral Description of Kernels
• Enumerating the kernels of a directed graph with no odd circuits

Cites work

• scientific article; zbMATH DE number 1445296 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A fixed-parameter algorithm for the directed feedback vertex set problem
• A graph-theoretic approach to default logic
• A machine program for theorem-proving
• A parity digraph has a kernel
• An efficient algorithm for the “stable roommates” problem
• An overview of backtrack search satisfiability algorithms
• Efficient CNF simplification based on binary implication graphs
• Graph theoretical structures in logic programs and default theories
• Graphes Noyau-Parfaits
• Kernels in planar digraphs
• On cliques in graphs
• On directed graphs with an independent covering set
• On generating all maximal independent sets
• On kernels and semikernels of digraphs
• On kernels in strongly connected graphs
• On kernels, defaults and even graphs
• On weakly ordered systems
• Perfect graphs, kernels, and cores of cooperative games
• Permanents, Pfaffian orientations, and even directed circuits
• Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
• Recent problems and results about kernels in directed graphs
• Solutions of irreflexive relations
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
• The number of maximal independent sets in connected graphs
• Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientes

Cited in

(9)

• Algorithmic aspects of small quasi-kernels
• Counting kernels in directed graphs with arbitrary orientations
• On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs
• Quasi-kernels in split graphs
• Kernels, truth and satisfaction
• Expressive power of digraph solvability
• Encoding argument graphs in logic
• Propositional discourse logic
• Quasi-transitive digraphs and their extensions

This page was built for publication: Finding kernels or solving SAT

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