8 citations · 36 across the 49 of their papers we have counts for
6 papers · 1 filter
Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited
Tesshu Hanaka, Yuto Okada, Yota Otachi +1
We study the parameterized complexity of the problems of finding a maximum common (induced) subgraph of two given graphs. Since these problems generalize several NP-complete proble…
Forcing a unique minimum spanning tree and a unique shortest path
Tatsuya Gima, Andreas Grigorjew, Yasuaki Kobayashi +7
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…
Hitting Geodesic Intervals in Structurally Restricted Graphs
Tatsuya Gima, Yasuaki Kobayashi, Yuto Okada +2
Given a graph , a set of vertex pairs, and an integer , Hitting Geodesic Intervals asks whether there is a set of size at most such that for e…
Finding Order-Preserving Subgraphs
Haruya Imamura, Yasuaki Kobayashi, Yota Otachi +5
(Induced) Subgraph Isomorphism and Maximum Common (Induced) Subgraph are fundamental problems in graph pattern matching and similarity computation. In graphs derived from time-seri…
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 ,…
Interval Graphs are Reconstructible
Irene Heinrich, Masashi Kiyomi, Yota Otachi +1
A graph is reconstructible if it is determined up to isomorphism by the multiset of its proper induced subgraphs. The reconstruction conjecture postulates that every graph of order…