The complexity of generalized clique packing
From MaRDI portal
Publication:1073049
DOI10.1016/0166-218X(85)90027-7zbMath0588.05037OpenAlexW2017992410MaRDI QIDQ1073049
Publication date: 1985
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(85)90027-7
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Edge-disjoint packings of graphs ⋮ Independent sets of maximum weight in (\(p,q\))-colorable graphs. ⋮ Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs ⋮ Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ The mutual exclusion scheduling problem for permutation and comparability graphs. ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs ⋮ Stable sets in two subclasses of banner-free graphs ⋮ (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization. ⋮ Scheduling jobs on identical machines with agreement graph ⋮ Maximum weight independent sets in hole- and dart-free graphs ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ The complexity of generalized clique covering ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs ⋮ Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes ⋮ On the stable set problem in special \(P_{5}\)-free graphs
Cites Work
- Unnamed Item
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Triangulated graphs and the elimination process
- On the Complexity of General Graph Factor Problems
- The NP-Completeness of Some Edge-Partition Problems
