Graphs without large apples and the maximum weight independent set problem
type: Item
instance of: scholarly article
title: Graphs without large apples and the maximum weight independent set problem
zbMATH Open document ID: 1298.05257
author: Vadim Lozin
author: Martin Milanič
author: Christopher Purcell
published in: Graphs and Combinatorics
publication date: 2014-09-19T00:00:00Z
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6346004
zbMATH Keywords: claw-free graphs
zbMATH Keywords: chordal graphs
zbMATH Keywords: independent set
zbMATH Keywords: polynomial algorithm
MaRDI profile type: Publication
full work available at URL: s00373-012-1263-y
OpenAlex ID: W2149269894
cites work: Graph searching and a min-max theorem for tree-width
cites work: Polynomial algorithm for finding the largest independent sets in graphs without forks
cites work: The Maximum Independent Set Problem in Planar Graphs
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Treewidth for graphs with small chordality
cites work: On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
cites work: Independent Sets of Maximum Weight in Apple-Free Graphs
cites work: Claw-free graphs. I: Orientable prismatic graphs
cites work: Claw-free graphs. II: Non-orientable prismatic graphs
cites work: Claw-free graphs. III: Circular interval graphs
cites work: Claw-free graphs. IV: Decomposition theorem
cites work: Claw-free graphs. V. Global structure
cites work: Diameter and treewidth in minor-closed graph families, revisited
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Q5365068
cites work: An upper bound on the number of cliques in a graph
cites work: Q4093489
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Q3216686
cites work: On the stability number of AH‐free graphs
cites work: Recent developments on graphs of bounded clique-width
cites work: Matching theory
cites work: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
cites work: Q2934676
cites work: Maximum regular induced subgraphs in \(2P_3\)-free graphs
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
cites work: A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
cites work: Graph minors. V. Excluding a planar graph
cites work: Decomposition by clique separators
cites work: A New Algorithm for Generating All the Maximal Independent Sets
cites work: An algorithm for finding clique cut-sets
DOI: 10.1007/S00373-012-1263-Y
Recommended article: Independent Sets of Maximum Weight in Apple-Free Graphs
Recommended article: On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five
Recommended article: The weighted maximum independent set problem in permutation graphs
Recommended article: Maximum weight independent sets in hole- and dart-free graphs
Recommended article: Maximum weightk-independent set problem on permutation graphs
Recommended article: On independent vertex sets in subclasses of apple-free graphs
Recommended article: Maximum weight independent sets in hole- and co-chair-free graphs
Recommended article: Maximum weight independent sets in odd-hole-free graphs without dart or without bull
Recommended article: Maximum weighted independent sets on transitive graphs and applications
description: scientific article; zbMATH DE number 6346004