Graphs without large apples and the maximum weight independent set problem
From MaRDI portal
Publication:742580
DOI10.1007/s00373-012-1263-yzbMath1298.05257OpenAlexW2149269894MaRDI QIDQ742580
Martin Milanič, Christopher Purcell, Vadim V. Lozin
Publication date: 19 September 2014
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00373-012-1263-y
Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Combining decomposition approaches for the maximum weight stable set problem, Set graphs. IV. Further connections with claw-freeness, Weighted independent sets in a subclass of \(P_6\)-free graphs, On the maximum independent set problem in subclasses of subcubic graphs, Independent Sets in Classes Related to Chair-Free Graphs, Maximum independent sets in subcubic graphs: new results, Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- Claw-free graphs. III: Circular interval graphs
- Claw-free graphs. IV: Decomposition theorem
- Claw-free graphs. V. Global structure
- Recent developments on graphs of bounded clique-width
- Decomposition by clique separators
- Graph minors. V. Excluding a planar graph
- Matching theory
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- On maximal independent sets of vertices in claw-free graphs
- An algorithm for finding clique cut-sets
- A partial k-arboretum of graphs with bounded treewidth
- Graph searching and a min-max theorem for tree-width
- Treewidth for graphs with small chordality
- Diameter and treewidth in minor-closed graph families, revisited
- Claw-free graphs. I: Orientable prismatic graphs
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Claw-free graphs. II: Non-orientable prismatic graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
- The Maximum Independent Set Problem in Planar Graphs
- 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
- On the stability number of AH‐free graphs
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- An upper bound on the number of cliques in a graph
- Maximum matching and a polyhedron with 0,1-vertices
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- 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
