Finding kernels or solving SAT
From MaRDI portal
Publication:414435
DOI10.1016/j.jda.2011.11.004zbMath1253.68160OpenAlexW2014402721MaRDI QIDQ414435
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
Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (5)
Algorithmic aspects of small quasi-kernels ⋮ Propositional discourse logic ⋮ Encoding Argument Graphs in Logic ⋮ On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs ⋮ Quasi-Transitive Digraphs and Their Extensions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph theoretical structures in logic programs and default theories
- The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
- On kernels and semikernels of digraphs
- A parity digraph has a kernel
- On generating all maximal independent sets
- Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
- Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientes
- On directed graphs with an independent covering set
- A graph-theoretic approach to default logic
- On kernels, defaults and even graphs
- An overview of backtrack search satisfiability algorithms
- Permanents, Pfaffian orientations, and even directed circuits
- Perfect graphs, kernels, and cores of cooperative games
- Kernels in planar digraphs
- Recent problems and results about kernels in directed graphs
- Solutions of irreflexive relations
- Efficient CNF Simplification Based on Binary Implication Graphs
- A fixed-parameter algorithm for the directed feedback vertex set problem
- An efficient algorithm for the “stable roommates” problem
- The number of maximal independent sets in connected graphs
- Graphes Noyau-Parfaits
- On kernels in strongly connected graphs
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- On weakly ordered systems
- On cliques in graphs
This page was built for publication: Finding kernels or solving SAT
