Finding kernels or solving SAT
DOI10.1016/J.JDA.2011.11.004zbMATH Open1253.68160OpenAlexW2014402721MaRDI QIDQ414435FDOQ414435
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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Permanents, Pfaffian orientations, and even directed circuits
- Perfect graphs, kernels, and cores of cooperative games
- Solutions of irreflexive relations
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Title not available (Why is that?)
- On cliques in graphs
- 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
- Graphes Noyau-Parfaits
- On kernels and semikernels of digraphs
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- On generating all maximal independent sets
- On weakly ordered systems
- On kernels, defaults and even graphs
- The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
- Graph theoretical structures in logic programs and default theories
- The number of maximal independent sets in connected graphs
- An efficient algorithm for the “stable roommates” problem
- 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
- On kernels in strongly connected graphs
- A parity digraph has a kernel
- A graph-theoretic approach to default logic
- An overview of backtrack search satisfiability algorithms
- Kernels in planar digraphs
- Efficient CNF Simplification Based on Binary Implication Graphs
- Title not available (Why is that?)
Cited In (8)
- Counting kernels in directed graphs with arbitrary orientations
- On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs
- Kernels, truth and satisfaction
- Algorithmic aspects of small quasi-kernels
- Quasi-Transitive Digraphs and Their Extensions
- Encoding Argument Graphs in Logic
- Propositional discourse logic
- Quasi-kernels in split graphs
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)
