The complexity of generalized clique covering

DOI10.1016/0166-218X(88)90086-8zbMath0685.68046OpenAlexW2006147407MaRDI QIDQ1262127

Jean Fonlupt, Derek Gordon Corneil

Publication date: 1989

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(88)90086-8

zbMATH Keywords

computational complexityNP-completenesschordal graphsclique cover

Mathematics Subject Classification ID

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 (25)

Faster exact algorithms for some terminal set problems ⋮ A linear-time algorithm for the weighted feedback vertex problem on interval graphs ⋮ Maximum \(h\)-colourable subgraph problem in balanced graphs ⋮ Reconfiguration of colorable sets in classes of perfect graphs ⋮ New upper bounds on feedback vertex numbers in butterflies ⋮ Structural parameterizations with modulator oblivion ⋮ Boundary classes for graph problems involving non-local properties ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Parameterized and exact algorithms for class domination coloring ⋮ Algorithmic aspects of the generalized clique-transversal problem on chordal graphs ⋮ On strictly chordality-\(k\) graphs ⋮ Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs ⋮ Unnamed Item ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Unnamed Item ⋮ Subset feedback vertex sets in chordal graphs ⋮ The maximum vertex coverage problem on bipartite graphs ⋮ Enumerating minimal subset feedback vertex sets ⋮ Algorithmic aspects of clique-transversal and clique-independent sets ⋮ The geodesic-transversal problem ⋮ Generalized vertex covering in interval graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

Cites Work

• Unnamed Item
• Unnamed Item
• Decomposition by clique separators
• \(K_ i\)-covers. I: Complexity and polytopes
• The complexity of generalized clique packing
• The maximum k-colorable subgraph problem for chordal graphs
• Algorithms on clique separable graphs
• Triangulated graphs and the elimination process
• Ki-covers. II.Ki-perfect graphs
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Edge-Deletion Problems
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: The complexity of generalized clique covering