Known Algorithms for Edge Clique Cover are Probably Optimal

DOI10.1137/130947076zbMath1329.05216arXiv1203.1754MaRDI QIDQ3464061

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk

Publication date: 20 January 2016

Published in: SIAM Journal on Computing, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.1754

zbMATH Keywords

parameterized complexity; exponential time hypothesis; kernelization; edge clique cover

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C62: Graph representations (geometric and intersection representations, etc.)