Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time

DOI10.1016/j.dam.2017.11.029zbMath1380.05147arXiv1602.05838OpenAlexW2964197964MaRDI QIDQ1701093

Andreas Brandstädt, Raffaele Mosca

Publication date: 22 February 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

polynomial timemaximum weight independent set problem\(\ell\)claw-free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Related Items

Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs ⋮ New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Unnamed Item ⋮ Simple games versus weighted voting games: bounding the critical threshold value ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs ⋮ Vertex cover at distance on \(H\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum regular induced subgraphs in \(2P_3\)-free graphs
• On diameters and radii of bridged graphs
• On maximal independent sets of vertices in claw-free graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
• From matchings to independent sets
• A reduction algorithm for the weighted stable set problem in claw-free graphs
• On graphs with polynomially solvable maximum-weight clique problem
• A New Algorithm for Generating All the Maximal Independent Sets
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Reducibility among Combinatorial Problems
• Independent Set in P₅-Free Graphs in Polynomial Time
• Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
• Independent Sets of Maximum Weight in Apple-Free Graphs
• Independent Sets of Maximum Weight in Apple-Free Graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph