4 papers
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
Fedor V. Fomin, Petr A. Golovach, Nikola JedliÄková +3
The classic theorem of Gallai and Milgram (1960) generalizes several fundamental results in Graph Theory, such as Dilworth's theorem on posets and KÅnig's theorem on matchings in…
Edge Clique Partition and Cover Beyond Independence
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
Covering and partitioning the edges of a graph into cliques are classical problems at the intersection of combinatorial optimization and graph theory, having been studied through a…
Packing Short Cycles
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +6
Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of v…
Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
Tomohiro Koana, Nidhi Purohit, Kirill Simonov
In Clique Cover, given a graph and an integer , the task is to partition the vertices of into cliques. Clique Cover on unit ball graphs has a natural interpretation…