Accueil

Ken-ichi Kawarabayashi

  1. K_6 minors in large 6-connected graphs.

    Tue, 03/13/2012 - 15:01 — SomNambul
    Authors: Serguei Norine, Robin Thomas, Ken-ichi Kawarabayashi, Paul Wollan
    Subjects: Combinatorics
    Abstract

    Jorgensen conjectured that every 6-connected graph with no K_6 minor has a
    vertex whose deletion makes the graph planar. We prove the conjecture for all
    sufficiently large graphs.

  2. Minimum k-way cut of bounded size is fixed-parameter tractable.

    Wed, 01/26/2011 - 16:01 — SomNambul
    Authors: Ken-ichi Kawarabayashi, Mikkel Thorup
    Subjects: Discrete Mathematics
    Abstract

    We consider a the minimum k-way cut problem for unweighted graphs with a size
    bound s on the number of cut edges allowed. Thus we seek to remove as few edges
    as possible so as to split a graph into k components, or report that this
    requires cutting more than s edges. We show that this problem is
    fixed-parameter tractable (FPT) in s. More precisely, for s=O(1), our algorithm
    runs in quadratic time while we have a different linear time algorithm for
    planar graphs and bounded genus graphs. Our tractability result stands in
    contrast to known W[1] hardness of related problems.

Math-arch

Syndicate content