Finding minimum clique capacity

DOI10.1007/S00493-012-2891-9MaRDI QIDQ2392036zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Sang-Il Oum, Paul Seymour

Publication date 6 August 2013

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-012-2891-9

zbMATH Keywords

capacityHadwiger's conjecturepacking

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

Let \(C\) be a clique of a graph \(G\). The capacity of \(C\) is defined to be \((| V(G) \setminus C| + | D|)/2\), where \(D\) is the set of vertices in \(V(G) \setminus C\) that have both a neighbor and a non-neighbor in \(C\). The main result of this paper states that there is an algorithm, with running time \(O(n^{3.5})\), which with input an \(n\)-vertex graph \(G\), finds a clique \(C\) in \(G\) with minimum capacity.

Recommendations

• Dominating cliques in graphs
• An exact algorithm for the minimum dominating clique problem
• An Exact Algorithm for the Minimum Dominating Clique Problem
• The clique-transversal set problem in claw-free graphs with degree at most 4
• 2-approximation algorithm for finding a clique with minimum weight of vertices and edges

Cites work

• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Packing seagulls

Cited in

(1)

• Packing seagulls

This page was built for publication: Finding minimum clique capacity

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