Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
From MaRDI portal
Publication:1701093
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
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 (9)
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 P5-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
This page was built for publication: Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
