Stable sets in \ISK4,wheel\-free graphs

DOI10.1007/S00453-016-0255-3MaRDI QIDQ1709574zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Martin Milanič, Irena Penev, Nicolas Trotignon

Publication date 6 April 2018

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Abstract: An ISK4 in a graph G is an induced subgraph of G that is isomorphic to a subdivision of K4 (the complete graph on four vertices). A wheel is a graph that consists of a chordless cycle, together with a vertex that has at least three neighbors in the cycle. A graph is {ISK4,wheel}-free if it has no ISK4 and does not contain a wheel as an induced subgraph. We give an O(|V(G)|^7)-time algorithm to compute the maximum weight of a stable set in an input weighted {ISK4,wheel}-free graph G with non-negative integer weights.

Recommendations

• Independent sets in \((P_4+P_4\),triangle)-free graphs
• Chromatic number of ISK4-free graphs
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• The maximum weight stable set problem in (\(P_6\), bull)-free graphs
• An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• A combinatorial algorithm for weighted stable sets in bipartite graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Berge trigraphs
• Combinatorial optimization with 2-joins
• Graph Classes: A Survey
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On graphs with no induced subdivision of \(K_4\)
• The Recognition of Series Parallel Digraphs
• Vertex elimination orderings for hereditary graph classes
• Wheel-free planar graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709574)