2.9k citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- The University of TokyoJP171 papers
- The Graduate University for Advanced Studies, SOKENDAIJP129 papers
- NTT Basic Research LaboratoriesJP96 papers
- Stanford UniversityUS80 papers
- Japan Science and Technology AgencyJP63 papers
- NTT (Japan)JP60 papers
- Centre National de la Recherche ScientifiqueFR55 papers
- New York UniversityUS49 papers
- New York University ShanghaiCN49 papers
- Hewlett-Packard (United Kingdom)GB41 papers
- East China Normal UniversityCN38 papers
- Japanese-French Laboratory for InformaticsJP38 papers
62 papers · 1 filter
Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
Alessio Conte, Roberto Grossi, Yasuaki Kobayashi +4
Graphlets of order in a graph are connected subgraphs induced by nodes (called -graphlets) or by edges (called edge -graphlets). They are among the interestin…
Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
Caroline Brosse, Alessio Conte, Vincent Limouzy +2
A set of vertices in a graph forms a potential maximal clique if there exists a minimal chordal completion in which it is a maximal clique. Potential maximal cliques were first int…
The Secretary Problem with Predictions
Kaito Fujii, Yuichi Yoshida
The value maximization version of the secretary problem is the problem of hiring a candidate with the largest value from a randomly ordered sequence of candidates. In this work, we…
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
Meike Hatzel, Lars Jaffke, Paloma T. Lima +4
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph , pairs of ve…
Online Risk-Averse Submodular Maximization
Tasuku Soma, Yuichi Yoshida
We present a polynomial-time online algorithm for maximizing the conditional value at risk (CVaR) of a monotone stochastic submodular function. Given i.i.d. samples from an und…
Constant Amortized Time Enumeration of Eulerian trails
Kazuhiro Kurita, Kunihiro Wasa
In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Here, two Eulerian trails are \emph{edge-distinct} if the edge sequences are…
Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Michael Kapralov, Robert Krauthgamer, Jakab Tardos +1
Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently bee…
Sensitivity Analysis of Submodular Function Maximization
Conor McMeel, Yuichi Yoshida
We study the recently introduced idea of worst-case sensitivity for monotone submodular maximization with cardinality constraint , which captures the degree to which the output…
Sensitivity Analysis of the Maximum Matching Problem
Yuichi Yoshida, Samson Zhou
We consider the sensitivity of algorithms for the maximum matching problem against edge and vertex modifications. Algorithms with low sensitivity are desirable because they are rob…
Finding Diverse Trees, Paths, and More
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita +1
Mathematical modeling is a standard approach to solve many real-world problems and {\em diversity} of solutions is an important issue, emerging in applying solutions obtained from…
Efficient Enumerations for Minimal Multicuts and Multiway Cuts
Kazuhiro Kurita, Yasuaki Kobayashi
Let be an undirected graph and let be a set of terminal pairs. A node/edge multicut is a subset of vertices/edges of whose removal destroy…
Fast and Private Submodular and -Submodular Functions Maximization with Matroid Constraints
Akbar Rafiey, Yuichi Yoshida
The problem of maximizing nonnegative monotone submodular functions under a certain constraint has been intensively studied in the last decade, and a wide range of efficient approx…
Hypergraph Clustering Based on PageRank
Yuuki Takai, Atsushi Miyauchi, Masahiro Ikeda +1
A hypergraph is a useful combinatorial object to model ternary or higher-order relations among entities. Clustering hypergraphs is a fundamental task in network analysis. In this s…
Average Sensitivity of Spectral Clustering
Pan Peng, Yuichi Yoshida
Spectral clustering is one of the most popular clustering methods for finding clusters in a graph, which has found many applications in data mining. However, the input graph in tho…
Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions
Kaito Fujii
This paper proposes a new framework for providing approximation guarantees of local search algorithms. Local search is a basic algorithm design technique and is widely used for var…
Computational Aspects of Geometric Algebra Products of Two Homogeneous Multivectors
Stephane Breuils, Vincent Nozick, Akihiro Sugimoto
Studies on time and memory costs of products in geometric algebra have been limited to cases where multivectors with multiple grades have only non-zero elements. This allows to des…
Constant Amortized Time Enumeration of Independent Sets for Graphs with Bounded Clique Number
Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura +1
In this study, we address the independent set enumeration problem. Although several efficient enumeration algorithms and careful analyses have been proposed for maximal independent…
Improved Analysis of Highest-Degree Branching for Feedback Vertex Set
Yoichi Iwata, Yusuke Kobayashi
Recent empirical evaluations of exact algorithms for Feedback Vertex Set have demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning heuris…
The Perfect Matching Reconfiguration Problem
Marthe Bonamy, Nicolas Bousquet, Marc Heinrich +5
We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a fl…
An Efficient Algorithm for Enumerating Chordal Bipartite Induced Subgraphs in Sparse Graphs
Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura +1
In this paper, we propose a characterization of chordal bipartite graphs and an efficient enumeration algorithm for chordal bipartite induced subgraphs. A chordal bipartite graph i…
Finding Cheeger Cuts in Hypergraphs via Heat Equation
Masahiro Ikeda, Atsushi Miyauchi, Yuuki Takai +1
Cheeger's inequality states that a tightly connected subset can be extracted from a graph using an eigenvector of the normalized Laplacian associated with . More specificall…
Spectral Sparsification of Hypergraphs
Tasuku Soma, Yuichi Yoshida
For an undirected/directed hypergraph , its Laplacian is defined such that its ``quadratic form'' $\boldsymbol{x}^\top L_G(\boldsym…
Efficient Enumeration of Subgraphs and Induced Subgraphs with Bounded Girth
Kazuhiro Kurita, Kunihiro Wasa, Alessio Conte +2
The girth of a graph is the length of its shortest cycle. Due to its relevance in graph theory, network analysis and practical fields such as distributed computing, girth-related p…
Polynomial-Time Algorithms for Submodular Laplacian Systems
Kaito Fujii, Tasuku Soma, Yuichi Yoshida
Let be an undirected graph, be the associated Laplacian matrix, and be a vector. Solving the Laplacian system $L_G x…