Browsing Bergen Open Research Archive by Author "Mouawad, Amer E."
Now showing items 1-2 of 2
-
Bisection of Bounded Treewidth Graphs by Convolutions
Eiben, Eduard; Lokshtanov, Daniel; Mouawad, Amer E. (Journal article; Peer reviewed, 2019)In the Bisection problem, we are given as input an edge-weighted graph G. The task is to find a partition of V(G) into two parts A and B such that ||A| - |B|| <= 1 and the sum of the weights of the edges with one endpoint ... -
Packing cycles faster than Erdos-Posa
Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2019)The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since the publication of the classic Erdös--Pósa theorem in 1965, this problem received significant attention ...