scientific article
From MaRDI portal
Publication:3686753
zbMath0569.05043MaRDI QIDQ3686753
Publication date: 1984
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
stable setoptimization problemspolynomial time algorithmperfect graphsrecognition algorithmminimum coloringmaximum weight cliquefinding clique cutsetsminimum weight fractional cover
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)
Related Items
Recognizing \(i\)-triangulated graphs in \(O(mn)\) time ⋮ Weighted independent sets in classes of \(P_6\)-free graphs ⋮ Jin Akiyama: a friend and his mathematics (on the occasion of his 60th birthday) ⋮ On independent vertex sets in subclasses of apple-free graphs ⋮ A fast algorithm for coloring Meyniel graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Recognizing claw-free perfect graphs ⋮ Even pairs in claw-free perfect graphs ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ A coloring algorithm for \(4 K_1\)-free line graphs ⋮ Finding induced paths of given parity in claw-free graphs ⋮ Classes of perfect graphs ⋮ Unnamed Item ⋮ Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs ⋮ On stable cutsets in claw-free graphs and planar graphs ⋮ Maximum weight independent sets in odd-hole-free graphs without dart or without bull ⋮ Critical hereditary graph classes: a survey ⋮ On the structure of (even hole, kite)-free graphs ⋮ Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Maximum weight independent sets in hole- and dart-free graphs ⋮ On \(H\)-topological intersection graphs ⋮ The intersection of two vertex coloring problems ⋮ Packing paths perfectly ⋮ On Distance-3 Matchings and Induced Matchings ⋮ The strong perfect graph conjecture: 40 years of attempts, and its resolution ⋮ On coloring a class of claw-free and hole-twin-free graphs ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds ⋮ The computational complexity of three graph problems for instances with bounded minors of constraint matrices
