3 papers
math.CO2018
Equitable Partitions into Matchings and Coverings in Mixed Graphs
Tamás Király, Yu Yokoi
Matchings and coverings are central topics in graph theory. The close relationship between these two has been key to many fundamental algorithmic and polyhedral results. For mixed…
cs.DS2018
Improving the Integrality Gap for Multiway Cut
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +1
In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of terminal nodes, and the goal is to partition the node set of th…
math.CO2015
Blocking optimal -arborescences
Attila Bernáth, Tamás Király
Given a digraph and a positive integer , an arc set is called a \textbf{-arborescence} if it is the disjoint union of spanning arborescences. The…