Graphs without large apples and the maximum weight independent set problem
DOI10.1007/S00373-012-1263-YzbMATH Open1298.05257OpenAlexW2149269894MaRDI QIDQ742580FDOQ742580
Authors: Vadim Lozin, Martin Milanič, Christopher Purcell 
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
Recommendations
- Independent sets of maximum weight in apple-free graphs
- Independent Sets of Maximum Weight in Apple-Free Graphs
- On the maximum weight independent set problem in graphs without induced cycles of length at least five
- The weighted maximum independent set problem in permutation graphs
- Maximum weight independent sets in hole- and dart-free graphs
- Maximum weightk-independent set problem on permutation graphs
- On independent vertex sets in subclasses of apple-free graphs
- Maximum weight independent sets in hole- and co-chair-free graphs
- Maximum weight independent sets in odd-hole-free graphs without dart or without bull
- Maximum weighted independent sets on transitive graphs and applications
Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)
Cites Work
- Matching theory
- Graph searching and a min-max theorem for tree-width
- Decomposition by clique separators
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth for graphs with small chordality
- Title not available (Why is that?)
- A New Algorithm for Generating All the Maximal Independent Sets
- Maximum matching and a polyhedron with 0,1-vertices
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- Claw-free graphs. V. Global structure
- Recent developments on graphs of bounded clique-width
- Graph minors. V. Excluding a planar graph
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- On maximal independent sets of vertices in claw-free graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- 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
- The Maximum Independent Set Problem in Planar Graphs
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
- Title not available (Why is that?)
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- Claw-free graphs. IV: Decomposition theorem
- Maximum independent sets in graphs of low degree
- Claw-free graphs. III: Circular interval graphs
- An algorithm for finding clique cut-sets
- Diameter and treewidth in minor-closed graph families, revisited
- Claw-free graphs. I: Orientable prismatic graphs
- Claw-free graphs. II: Non-orientable prismatic graphs
- Title not available (Why is that?)
- An upper bound on the number of cliques in a graph
- On the stability number of AH‐free graphs
Cited In (9)
- Set graphs. IV. Further connections with claw-freeness
- On independent vertex sets in subclasses of apple-free graphs
- Combining decomposition approaches for the maximum weight stable set problem
- Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
- Weighted independent sets in a subclass of \(P_6\)-free graphs
- On the maximum independent set problem in subclasses of subcubic graphs
- Independent sets of maximum weight in apple-free graphs
- Independent Sets of Maximum Weight in Apple-Free Graphs
- Independent Sets in Classes Related to Chair-Free Graphs
This page was built for publication: Graphs without large apples and the maximum weight independent set problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q742580)
