Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs

DOI10.1007/s00453-016-0255-3zbMath1383.05214arXiv1602.02916OpenAlexW2962772544WikidataQ59885431 ScholiaQ59885431MaRDI QIDQ1709574

Nicolas Trotignon, Martin Milanič, Irena Penev

Publication date: 6 April 2018

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

\(O(|V(G)|^7)\)-time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)

Cites Work

• Unnamed Item
• Unnamed Item
• On graphs with no induced subdivision of \(K_4\)
• Combinatorial optimization with 2-joins
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Wheel-free planar graphs
• A combinatorial algorithm for weighted stable sets in bipartite graphs
• Vertex elimination orderings for hereditary graph classes
• A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs
• The Recognition of Series Parallel Digraphs
• Graph Classes: A Survey
• Berge trigraphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs