Stable sets in \ISK4,wheel\-free graphs

DOI10.1007/S00453-016-0255-3zbMATH Open1383.05214DBLPjournals/algorithmica/MilanicPT18arXiv1602.02916OpenAlexW2962772544WikidataQ59885431 ScholiaQ59885431MaRDI QIDQ1709574FDOQ1709574

Authors: Martin Milanič, Irena Penev, Nicolas Trotignon 

Publication date: 6 April 2018

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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\)

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)

Cites Work

• Graph Classes: A Survey
• On graphs with no induced subdivision of \(K_4\)
• 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
• Title not available (Why is that?)
• Berge trigraphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• The Recognition of Series Parallel Digraphs
• Title not available (Why is that?)
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Combinatorial optimization with 2-joins
• Wheel-free planar graphs
• A combinatorial algorithm for weighted stable sets in bipartite graphs
• Vertex elimination orderings for hereditary graph classes

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)