3 citations · 5 across the 3 of their papers we have counts for
6 papers
Independent set reconfiguration on directed graphs
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi +4
\textsc{Directed Token Sliding} asks, given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a…
A Note on Exponential-Time Algorithms for Linearwidth
Yasuaki Kobayashi, Yu Nakahata
In this note, we give an algorithm that computes the linearwidth of input -vertex graphs in time , which improves a trivial -time algorithm, where and $m…
Compiling Crossing-free Geometric Graphs with Connectivity Constraint for Fast Enumeration, Random Sampling, and Optimization
Yu Nakahata, Takashi Horiyama, Shin-ichi Minato +1
Given points in the plane, we propose algorithms to compile connected crossing-free geometric graphs into directed acyclic graphs (DAGs). The DAGs allow efficient counting, enu…
Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration
Yu Nakahata, Jun Kawahara, Takashi Horiyama +1
Given graphs and , we propose a method to implicitly enumerate topological-minor-embeddings of in using decision diagrams. We show a useful application of our method…
Decomposing a Graph into Unigraphs
Takashi Horiyama, Jun Kawahara, Shin-ichi Minato +1
Unigraphs are graphs uniquely determined by their own degree sequence up to isomorphism. There are many subclasses of unigraphs such as threshold graphs, split matrogenic graphs, m…
Enumerating Graph Partitions Without Too Small Connected Components Using Zero-suppressed Binary and Ternary Decision Diagrams
Yu Nakahata, Jun Kawahara, Shoji Kasahara
Partitioning a graph into balanced components is important for several applications. For multi-objective problems, it is useful not only to find one solution but also to enumerate…