Browsing Bergen Open Research Archive by Author "Pilipczuk, Michal Pawel"
Now showing items 19 of 9

Computing cutwidth and pathwidth of semicomplete digraphs via degree orderings
Pilipczuk, Michal Pawel (Conference object; Peer reviewed; Journal article, 2013)The notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semicomplete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, ... 
Exploring Subexponential Parameterized Complexity of Completion Problems
Drange, Pål Grønås; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve (Peer reviewed; Journal article, 20140219)Let F be a family of graphs. In the FCompletion problem, we are given an nvertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the resulting graph does not contain a graph ... 
Largest chordal and interval subgraphs faster than 2n
Bliznets, Ivan; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve (Peer reviewed; Journal article, 20150822)We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time O(2λn) for some λ< 1. These are the first algorithms breaking the trivial 2nnO(1) ... 
On cutwidth parameterized by vertex cover
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Saurabh, Saket (Peer reviewed; Journal article, 201404)We study the CUTWIDTH problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two ... 
Parameterized complexity of Eulerian deletion problems
Cygan, Marek; Pilipczuk, Marcin; Marx, Dániel; Pilipczuk, Michal Pawel; Schlotter, Ildikó (Peer reviewed; Journal article, 201401)We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity ... 
Solving the 2disjoint connected subgraphs problem faster than 2ⁿ
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Wojtaszczyk, Jakub Onufry (Peer reviewed; Journal article, 201410)The 2DISJOINT CONNECTED SUBGRAPHS problem, given a graph along with two disjoint sets of terminals Z1,Z2, asks whether it is possible to find disjoint sets A1,A2, such that Z1 ⊆ A1, Z2 ⊆ A2 and A1,A2 induce connected ... 
Subexponentialtime parameterized algorithm for Steiner tree on planar graphs
Pilipczuk, Marcin; Pilipczuk, Michal Pawel; van Leeuwen, Erik Jan; Sankowski, Piotr (Conference object; Peer reviewed; Journal article, 2013)The wellknown bidimensionality theory provides a method for designing fast, subexponentialtime parameterized algorithms for a vast number of NPhard problems on sparse graph classes such as planar graphs, bounded genus ... 
Tight bounds for parameterized complexity of Cluster Editing
Fomin, Fedor; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Villanger, Yngve (Conference object; Peer reviewed; Journal article, 2013)In the Correlation Clustering problem, also known as Cluster Editing, we are given an undirected graph G and a positive integer k; the task is to decide whether G can be transformed into a cluster graph, i.e., a disjoint ... 
Tournaments and Optimality: New Results in Parameterized Complexity
Pilipczuk, Michal Pawel (Doctoral thesis; Peer reviewed, 20131122)