Blar i Bergen Open Research Archive på forfatter "Golovach, Petr"

Viser treff 41-53 av 53

    • 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, 2012-09)
      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 apex-minor-free graphs, a general class ...

    • Parameterized k-Clustering: Tractability Island 

      Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Peer reviewed; Journal article, 2019)
      In k-Clustering 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} ...

    • Partitioning H-Free Graphs of Bounded Diameter 

      Brause, Christoph; Golovach, Petr; Martin, Barnaby; Paulusma, Daniël; Smith, Siani (Journal article; Peer reviewed, 2021)
      A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, ...

    • Present-biased optimization 

      Fomin, Fedor; Fraigniaud, Pierre; Golovach, Petr (Journal article; Peer reviewed, 2022)
      This paper explores the behavior of present-biased agents, that is, agents who erroneously anticipate the costs of future actions compared to their real costs. Specifically, we extend the original framework proposed by ...

    • (Re)packing Equal Disks into Rectangle 

      Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Zehavi, Meirav (Journal article; Peer reviewed, 2022)
      The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following ...

    • Recognizing Proper Tree-Graphs 

      Chaplick, Steven; Golovach, Petr; Hartmann, Tim; Knop, Dusan (Journal article; Peer reviewed, 2020)
      We investigate the parameterized complexity of the recognition problem for the proper H-graphs. The H-graphs are the intersection graphs of connected subgraphs of a subdivision of a multigraph H, and the properness means ...

    • Refined Complexity of PCA with Outliers 

      Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill (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 ...

    • Refined notions of parameterized enumeration kernels with applications to matching cut enumeration 

      Golovach, Petr; Komusiewicz, Christian; Kratsch, Dieter; Le, Van Bang (Journal article; Peer reviewed, 2021)
      An enumeration kernel as defined by Creignou et al. (2017) [11] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a ...

    • Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs 

      Fomin, Fedor; Golovach, Petr (Journal article; Peer reviewed, 2020)
      We study algorithmic properties of the graph class Chordal-ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. We discover that ...

    • Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs 

      Fomin, Fedor; Golovach, Petr (Journal article; Peer reviewed, 2021)
      We study algorithmic properties of the graph class CHORDAL−ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fll-in at most k. It appears that a ...

    • Subgraph Complementation 

      Fomin, Fedor; Golovach, Petr; Strømme, Torstein J. F.; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2020-02)
      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 ...

    • A survey of parameterized algorithms and the complexity of edge modification 

      Crespelle, Christophe; Drange, Pål Grønås; Fomin, Fedor; Golovach, Petr (Journal article; Peer reviewed, 2023)
      The survey is a comprehensive overview of the developing area of parameterized algorithms for graph modification problems. It describes state of the art in kernelization, subexponential algorithms, and parameterized ...

    • Variants of plane diameter completion 

      Golovach, Petr; Requile, Clement; Thilikos, Dimitrios M. (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 ...