2.9k citations
- 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…