15 citations · 65 across the 24 of their papers we have counts for
5 papers · 1 filter
Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph
Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
In this paper, we address the problem of enumerating all induced subtrees in an input k-degenerate graph, where an induced subtree is an acyclic and connected induced subgraph. A g…
A New Approach to Efficient Enumeration by Push-out Amortization
Takeaki Uno
Enumeration algorithms have been one of recent hot topics in theoretical computer science. Different from other problems, enumeration has many interesting aspects, such as the comp…
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…
An Efficient Algorithm for Enumerating Chordless Cycles and Chordless Paths
Takeaki Uno, Hiroko Satoh
A chordless cycle (induced cycle) of a graph is a cycle without any chord, meaning that there is no edge outside the cycle connecting two vertices of the cycle. A chordless pat…
Polynomial Delay Algorithm for Listing Minimal Edge Dominating sets in Graphs
Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary +2
The Transversal problem, i.e, the enumeration of all the minimal transversals of a hypergraph in output-polynomial time, i.e, in time polynomial in its size and the cumulated size…