Blar i Department of Informatics på forfatter "Fomin, Fedor"

Viser treff 21-40 av 72

    • Exact algorithms for treewidth and minimum fill-in 

      Fomin, Fedor; Todinca, Ioan; Kratsch, Dieter; Villanger, Yngve (Journal article, 2006)

    • Exact Exponential Algorithms for Clustering Problems 

      Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Purohit, Nidhi; Saurabh, Saket (Journal article; Peer reviewed, 2022)
      In this paper we initiate a systematic study of exact algorithms for some of the well known clustering problems, namely k-MEDIAN and k-MEANS. In k-MEDIAN, the input consists of a set X of n points belonging to a metric ...

    • Exploring Subexponential Parameterized Complexity of Completion Problems 

      Drange, Pål Grønås; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve (Peer reviewed; Journal article, 2014-02-19)
      Let F be a family of graphs. In the F-Completion problem, we are given an n-vertex 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 ...

    • Finding Induced Subgraphs via Minimal Triangulations 

      Fomin, Fedor; Villanger, Yngve (Peer reviewed; Journal article, 2010)
      Potential maximal cliques and minimal separators are combinatorial objects which were introduced and studied in the realm of minimal triangulation problems in- cluding Minimum Fill-in and Treewidth. We discover unexpected ...

    • A Fixed-Parameter Perspective on #BIS 

      Curticapean, Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John (Peer reviewed; Journal article, 2019-07-18)
      The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class #RHΠ1. It is believed that #BIS ...

    • FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges 

      Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Koana, Tomohiro (Journal article; Peer reviewed, 2023)
      We study the α-Fixed Cardinality Graph Partitioning (α-FCGP) problem, the generic local graph partitioning problem introduced by Bonnet et al. [Algorithmica 2015]. In this problem, we are given a graph G, two numbers k,p ...

    • FPT Approximation for Fair Minimum-Load Clustering 

      Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2022)
      In this paper, we consider the Minimum-Load k-Clustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k > 0 that denotes the number of ...

    • Going Far from Degeneracy 

      Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)
      An undirected graph $G$ is $d$-degenerate if every subgraph of $G$ has a vertex of degree at most $d$. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy $d>1$ contains a cycle of length at ...

    • Going Far From Degeneracy 

      Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Peer reviewed; Journal article, 2019-09-06)
      An undirected graph G is d-degenerate 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 ...

    • How to find a good explanation for clustering? 

      Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2023)
      k-means and k-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependencies on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, ...

    • Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves 

      Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Raible, Daniel; Saurabh, Saket; Villanger, Yngve (Peer reviewed; Journal article, 2009)
      The {\sc \(k\)-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least \(k\) leaves in a given digraph. The problem has recently received much attention from the ...

    • Kernelization for Spreading Points 

      Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Zehavi, Meirav (Journal article; Peer reviewed, 2023)
      We consider the following problem about dispersing points. Given a set of points in the plane, the task is to identify whether by moving a small number of points by small distance, we can obtain an arrangement of points ...

    • Kernelization of Graph Hamiltonicity: Proper H-Graphs 

      Chaplick, Steven; Fomin, Fedor; Golovach, Petr; Knop, Dusan; Zeman, Peter (Journal article; Peer reviewed, 2021)
      We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization ...

    • Kernelization of Whitney Switches 

      Fomin, Fedor; Golovach, Petr (Journal article; Peer reviewed, 2020)
      A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs G and H are 2-isomorphic, or equivalently, their cycle matroids are isomorphic, if and only if G can be transformed into H by a series of operations ...

    • Kernelization of Whitney Switches 

      Fomin, Fedor; Golovach, Petr (Journal article; Peer reviewed, 2021)
      A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs $G$ and $H$ are 2-isomorphic, or equivalently, their cycle matroids are isomorphic if and only if $G$ can be transformed into $H$ by a series of ...

    • Kernelizing Temporal Exploration Problems 

      Arrighi, Emmanuel Jean Paul Pierre; Fomin, Fedor; Golovach, Petr; Wolf, Petra Henrike Karola (Journal article; Peer reviewed, 2023)
      We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs 𝒢 = (G₁, G₂, … , G_L) that share a common vertex set but might have different edge ...

    • Largest chordal and interval subgraphs faster than 2n 

      Bliznets, Ivan; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve (Peer reviewed; Journal article, 2015-08-22)
      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) ...

    • Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms 

      Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2022)
      We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree ...

    • Longest Cycle Above Erdös-Gallai Bound 

      Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill (Journal article; Peer reviewed, 2022)
      In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2^𝒪(k)⋅n^𝒪(1) decides whether a 2-connected ...

    • Lossy Kernelization of Same-Size Clustering 

      Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2023)
      In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) ...