897 citations
- Stanford UniversityUS18 papers
- Hewlett-Packard (United Kingdom)GB16 papers
- Bristol Laboratories (United Kingdom)GB13 papers
- The University of TokyoJP11 papers
- Hewlett-Packard (United States)US6 papers
- Hitotsubashi UniversityJP5 papers
- Japan Science and Technology AgencyJP5 papers
- The University of MelbourneAU5 papers
- The University of QueenslandAU5 papers
- Centre for Quantum Computation and Communication TechnologyAU3 papers
- NTT Basic Research LaboratoriesJP3 papers
- Tohoku UniversityJP3 papers
7 papers · 1 filter
An improved lower bound for one-dimensional online unit clustering
Jun Kawahara, Koji M. Kobayashi
The online unit clustering problem was proposed by Chan and Zarrabi-Zadeh (WAOA2007 and Theory of Computing Systems 45(3), 2009), which is defined as follows: "Points" are given on…
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…
Variable-Order de Bruijn Graphs
Christina Boucher, Alex Bowe, Travis Gagie +2
The de Bruijn graph of a set of strings is a key data structure in genome assembly that represents overlaps between all the -length substrings of . Construction and…
A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs
Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary +2
An output-polynomial algorithm for the listing of minimal dominating sets in graphs is a challenging open problem and is known to be equivalent to the well-known Transversal proble…
Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling
Takuya Akiba, Yoichi Iwata, Yuichi Yoshida
We propose a new exact method for shortest-path distance queries on large-scale networks. Our method precomputes distance labels for vertices by performing a breadth-first search f…