Data reduction and exact algorithms for clique cover

DOI10.1145/1412228.1412236zbMath1284.05286OpenAlexW2040081895MaRDI QIDQ5406188

Rolf Niedermeier, Jens Gramm, Falk Hüffner, Jiong Guo

Publication date: 1 April 2014

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1412228.1412236

zbMATH Keywords

data reductionfixed-parameter tractabilityclique cover

Mathematics Subject Classification ID

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

Related Items (27)

Unsupervised feature selection for efficient exploration of high dimensional data ⋮ An overview of graph covering and partitioning ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Compressed cliques graphs, clique coverings and positive zero forcing ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ Parameterized analysis and crossing minimization problems ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ Calculating approximation guarantees for partial set cover of pairs ⋮ Clique Cover and Graph Separation ⋮ Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs ⋮ The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study ⋮ Edge-clique covers of the tensor product ⋮ Mod/Resc parsimony inference: theory and application ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Parameterized low-rank binary matrix approximation ⋮ Positive Zero Forcing and Edge Clique Coverings ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ On the kernel size of clique cover reductions for random intersection graphs ⋮ Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy ⋮ Techniques for determining the minimum rank of a small graph ⋮ Fast constructive and improvement heuristics for edge clique covering ⋮ On the complexity of directed intersection representation of DAGs ⋮ On the complete width and edge clique cover problems ⋮ \(0\text{-}1\) multilinear programming as a unifying theory for LAD pattern generation ⋮ Large-scale clique cover of real-world networks ⋮ On the tractability of covering a graph with 2-clubs ⋮ On some FPT problems without polynomial Turing compressions

This page was built for publication: Data reduction and exact algorithms for clique cover