5 citations · 14 across the 9 of their papers we have counts for
11 papers
Reconfiguring Multiple Connected Components with Size Multiset Constraints
Yu Nakahata
We propose a novel generalization of Independent Set Reconfiguration (ISR): Connected Components Reconfiguration (CCR). In CCR, we are given a graph , two vertex subsets and…
Computing Time-varying Network Reliability using Binary Decision Diagrams
Yu Nakahata, Shun Arizono, Shoji Kasahara
Computing the reliability of a time-varying network, taking into account its dynamic nature, is crucial for networks that change over time, such as space networks, vehicular ad-hoc…
ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems
Takehiro Ito, Jun Kawahara, Yu Nakahata +4
This paper proposes an algorithmic framework for various reconfiguration problems using zero-suppressed binary decision diagrams (ZDDs), a data structure for families of sets. In g…
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…
Reconfiguring (non-spanning) arborescences
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi +3
In this paper, we investigate the computational complexity of subgraph reconfiguration problems in directed graphs. More specifically, we focus on the problem of reconfiguring arbo…
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…
On the Clique-Width of Unigraphs
Yu Nakahata
Clique-width is a well-studied graph parameter. For graphs of bounded clique-width, many problems that are NP-hard in general can be polynomial-time solvable. The fact motivates se…
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…