Showing 2025Show all
3 papers · 1 filter
cs.DS2025
Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes
Toranosuke Kokai, Akira Suzuki, Takahiro Suzuki +2
In the context of algorithm theory, various studies have been conducted on spanning trees with desirable properties. In this paper, we consider the \textsc{Minimum Cover Spanning T…
cs.CC2025
Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules
Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga +3
In reconfiguration problems, we are given two feasible solutions to a graph problem and asked whether one can be transformed into the other via a sequence of feasible intermediate…
cs.DS2025
Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules
Tatsuhiro Suga, Akira Suzuki, Yuma Tamura +1
In a reconfiguration problem, we are given two feasible solutions of a combinatorial problem and our goal is to determine whether it is possible to reconfigure one into the other,…