Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time

DOI10.1016/j.tcs.2021.05.027OpenAlexW3164805113MaRDI QIDQ2043008

Andreas Brandstädt, Raffaele Mosca

Publication date: 22 July 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

polynomial time algorithmtriangle-free graphsanti-neighborhood approach\( S_{1, 2, 4}\)-free graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Combining decomposition approaches for the maximum weight stable set problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the closure of triangle-free graphs under substitution
• Paw-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Geometric algorithms and combinatorial optimization
• Modular decomposition and transitive orientation
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time
• Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• A note on triangle-free and bipartite graphs
• Independent sets in \((P_4+P_4\),triangle)-free graphs
• An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
• From matchings to independent sets
• The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs
• Graph Classes: A Survey
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Independence and Efficient Domination on P ₆ -free Graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Reducibility among Combinatorial Problems
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time