6 papers
Frameworks to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi +4
Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world probl…
Forcing a unique minimum spanning tree and a unique shortest path
Tatsuya Gima, Andreas Grigorjew, Yasuaki Kobayashi +8
A forcing set in a combinatorial problem is a set of elements such that there is a unique solution that contains all the elements in . An anti-forcing set is the symmetric c…
Broadcasting under Structural Restrictions
Yudai Egami, Tatsuya Gima, Tesshu Hanaka +7
In the Telephone Broadcast problem we are given a graph with a designated source vertex . Our goal is to transmit a message, which is initially known only to ,…
Finding a Minimum Spanning Tree with a Small Non-Terminal Set
Tesshu Hanaka, Yasuaki Kobayashi
In this paper, we study the problem of finding a minimum weight spanning tree that contains each vertex in a given subset of vertices as an internal vertex. This probl…
Structural Parameterizations of Vertex Integrity
Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi +3
The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a sma…
Basis sequence reconfiguration in the union of matroids
Tesshu Hanaka, Yuni Iwamasa, Yasuaki Kobayashi +2
Given a graph and two spanning trees and in , Spanning Tree Reconfiguration asks whether there is a step-by-step transformation from to such that all inter…