scientific article; zbMATH DE number 3908479

MaRDI QIDQ3686753zbMATH OpenFDO

Authors Sue Whitesides

Publication date 1984

zbMATH Keywords

optimization problemspolynomial time algorithmstable setperfect graphsrecognition algorithmminimum coloringmaximum weight cliquefinding clique cutsetsminimum weight fractional cover

Mathematics Subject Classification ID

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)

Recommendations

• scientific article; zbMATH DE number 3882470
• scientific article; zbMATH DE number 3888924
• scientific article; zbMATH DE number 3893237
• On the Maximum Weight Clique Problem
• Optimizing weakly triangulated graphs

Cited in

(36)

• Approximation of knapsack problems with conflict and forcing graphs
• On independent vertex sets in subclasses of apple-free graphs
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• Even pairs in claw-free perfect graphs
• The complexity of some graph problems with bounded minors of their constraint matrices
• On the structure of (even hole, kite)-free graphs
• Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
• The time complexity of oriented chromatic number for acyclic oriented connected subcubic subgraphs of grids
• On \(H\)-topological intersection graphs
• scientific article; zbMATH DE number 3888924 (Why is no real title available?)
• Completely separable graphs
• Combining decomposition approaches for the maximum weight stable set problem
• Recognizing \(i\)-triangulated graphs in \(O(mn)\) time
• Weighted independent sets in classes of \(P_6\)-free graphs
• A coloring algorithm for \(4 K_1\)-free line graphs
• A fast algorithm for coloring Meyniel graphs
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
• Disjoint clique cutsets in graphs without long holes
• The intersection of two vertex coloring problems
• Maximum weight independent sets in hole- and dart-free graphs
• New applications of clique separator decomposition for the maximum weight stable set problem
• Critical hereditary graph classes: a survey
• Jin Akiyama: a friend and his mathematics (on the occasion of his 60th birthday)
• Packing paths perfectly
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Classes of perfect graphs
• On distance-3 matchings and induced matchings
• The strong perfect graph conjecture: 40 years of attempts, and its resolution
• Recognizing claw-free perfect graphs
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• scientific article; zbMATH DE number 2079402 (Why is no real title available?)
• On stable cutsets in claw-free graphs and planar graphs
• On coloring a class of claw-free and hole-twin-free graphs
• Finding induced paths of given parity in claw-free graphs
• The computational complexity of three graph problems for instances with bounded minors of constraint matrices

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3686753)