970 citations · 1.7k across the 49 of their papers we have counts for
3 papers · 2 filters
Beyond the Euler characteristic: Approximating the genus of general graphs
Ken-ichi Kawarabayashi, Anastasios Sidiropoulos
Computing the Euler genus of a graph is a fundamental problem in graph theory and topology. It has been shown to be NP-hard by [Thomassen '89] and a linear-time fixed-parameter alg…
Efficient SimRank Computation via Linearization
Takanori Maehara, Mitsuru Kusumoto, Ken-ichi Kawarabayashi
SimRank, proposed by Jeh and Widom, provides a good similarity measure that has been successfully used in numerous applications. While there are many algorithms proposed for comput…
Deterministic Edge Connectivity in Near-Linear Time
Ken-ichi Kawarabayashi, Mikkel Thorup
We present a deterministic near-linear time algorithm that computes the edge-connectivity and finds a minimum cut for a simple undirected unweighted graph G with n vertices and m e…