A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs

DOI10.1007/978-3-319-12340-0_34zbMath1364.68232OpenAlexW2248791588WikidataQ59898745 ScholiaQ59898745MaRDI QIDQ2945208

Kristina Vušković, Steéphan Thomassé, Nicolas Trotignon

Publication date: 9 September 2015

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

Full work available at URL: http://eprints.whiterose.ac.uk/82507/1/bullFreewg.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs ⋮ Maximum weight independent sets in odd-hole-free graphs without dart or without bull ⋮ A polynomial Turing-kernel for weighted independent set in bull-free graphs ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Parameterized certificate dispersal and its variants ⋮ Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor

This page was built for publication: A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs