Browsing Bergen Open Research Archive by Author "Golovach, Petr"
Now showing items 115 of 15

Approximating Acyclicity Parameters of Sparse Hypergraphs
Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios (Conference object; Peer reviewed; Journal article, 2009)The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized ... 
Clustering to Given Connectivities
Golovach, Petr; Thilikos, Dimitrios M. (Peer reviewed; Journal article, 2019)We define a general variant of the graph clustering problem where the criterion of density for the clusters is (high) connectivity. In Clustering to Given Connectivities, we are given an nvertex graph G, an integer k, and ... 
Connecting Vertices by Independent Trees
Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Saurabh, Saket (Conference object, 2014)We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T1, . . . , Ts of G are completely independent spanning trees of U if each of them contains U , and ... 
Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals
Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (Peer reviewed; Journal article, 2019)Perturbed graphic matroids are binary matroids that can be obtained from a graphic matroid by adding a noise of small rank. More precisely, an rrank perturbed graphic matroid M is a binary matroid that can be represented ... 
Cyclability in Graph Classes
Crespelle, Christophe Dominique; Feghali, Carl; Golovach, Petr (Peer reviewed; Journal article, 2019)A subset T subseteq V(G) of vertices of a graph G is said to be cyclable if G has a cycle C containing every vertex of T, and for a positive integer k, a graph G is kcyclable if every subset of vertices of G of size at ... 
Editing to Eulerian Graphs
Dabrowski, Konrad K.; Golovach, Petr; van' t Hof, Pim; Paulusma, Daniël (Conference object, 2014)We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let ea, ed and vd denote the operations edge addition, edge deletion and ... 
Enumerating minimal connected dominating sets in graphs of bounded chordality
Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter (Conference object; Peer reviewed; Journal article, 2015)Listing, generating or enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration ... 
Going Far From Degeneracy
Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Peer reviewed; Journal article, 20190906)An undirected graph G is ddegenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erd\H{o}s and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least ... 
Modification to planarity is fixed parameter tractable
Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M (Peer reviewed; Journal article, 2019)A replacement action is a function L that maps each kvertex labeled graph to another kvertex graph. We consider a general family of graph modification problems, called LReplacement to C, where the input is a graph G and ... 
Parameterized complexity of secluded connectivity problems
Fomin, Fedor; Golovach, Petr; Karpov, Nikolay; Kulikov, Alexander S (Conference object; Peer reviewed; Journal article, 2015)The Secluded Path problem introduced by Chechik et al. in [ESA 2013] models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of ... 
Parameterized complexity of the spanning tree congestion problem
Bodlaender, Hans L.; Fomin, Fedor; Golovach, Petr; Otachi, Yota; van Leeuwen, Erik Jan (Peer reviewed; Journal article, 201209)We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apexminorfree graphs, a general class ... 
Parameterized kClustering: Tractability Island
Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Peer reviewed; Journal article, 2019)In kClustering we are given a multiset of n vectors X subset Z^d and a nonnegative number D, and we need to decide whether X can be partitioned into k clusters C_1, ..., C_k such that the cost sum_{i=1}^k min_{c_i in R^d} ... 
Refined Complexity of PCA with Outliers
Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill (Conference object; Peer reviewed; Journal article, 2019)Principal component analysis (PCA) is one of the most fundamental procedures in exploratory data analysis and is the basic step in applications ranging from quantitative finance and bioinformatics to image analysis and ... 
Subgraph Complementation
Fomin, Fedor; Golovach, Petr; Strømme, Torstein J. F.; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 202002)A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is there ... 
Variants of plane diameter completion
Golovach, Petr; Requile, Clement; Thilikos, Dimitrios M. (Conference object; Peer reviewed; Journal article, 2015)The Plane Diameter Completion problem asks, given a plane graph G and a positive integer d, if it is a spanning subgraph of a plane graph H that has diameter at most d. We examine two variants of this problem where the ...