Algorithmic aspects of small quasi-kernels

DOI10.1007/978-3-031-15914-5_27arXiv2107.03793MaRDI QIDQ6043190

Frédéric Meunier, Hélène Langlois, Romeo Rizzi, Stéphane Vialette

Publication date: 5 May 2023

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2107.03793

zbMATH Keywords

computational complexitydigraphquasi-kernel

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

Results on the small quasi-kernel conjecture

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Finding kernels or solving SAT
• Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
• Optimization, approximation, and complexity classes
• The list chromatic index of a bipartite multigraph
• Towards the small quasi-kernel conjecture
• Perfect graphs, kernels, and cores of cooperative games
• Disjoint quasi-kernels in digraphs
• Short proofs of classical theorems
• On the number of quasi-kernels in digraphs
• Reducibility among Combinatorial Problems
• Analytical approach to parallel repetition

This page was built for publication: Algorithmic aspects of small quasi-kernels