Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time
type: Item
instance of: scholarly article
title: Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time
author: Andreas Brandstädt
author: Raffaele Mosca
published in: Theoretical Computer Science
publication date: 2021-07-22T00:00:00Z
full work available at URL: https://arxiv.org/abs/1806.09472
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7373863
zbMATH Keywords: \( S_{1, 2, 4}\)-free graphs
zbMATH Keywords: triangle-free graphs
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: anti-neighborhood approach
MaRDI profile type: Publication
OpenAlex ID: W3164805113
cites work: Q3056948
cites work: Polynomial algorithm for finding the largest independent sets in graphs without forks
cites work: On easy and hard hereditary classes of graphs with respect to the independent set problem
cites work: Graph Classes: A Survey
cites work: Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time
cites work: Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
cites work: Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
cites work: Q4198056
cites work: Geometric algorithms and combinatorial optimization
cites work: Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs
cites work: The Number of Maximal Independent Sets in Triangle-Free Graphs
cites work: Reducibility among Combinatorial Problems
cites work: Independence and Efficient Domination on P 6 -free Graphs
cites work: Independent Set in P5-Free Graphs in Polynomial Time
cites work: From matchings to independent sets
cites work: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
cites work: The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs
cites work: Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: Independent sets in \((P_4+P_4\),triangle)-free graphs
cites work: A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
cites work: An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
cites work: Modular decomposition and transitive orientation
cites work: Q3683903
cites work: Paw-free graphs
cites work: On the closure of triangle-free graphs under substitution
cites work: Q4770411
cites work: A note on triangle-free and bipartite graphs
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
DOI: 10.1016/J.TCS.2021.05.027
description: scientific article; zbMATH DE number 7373863