5 citations · 24 across the 16 of their papers we have counts for
19 papers
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…
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 ,…
Complexity of Jelly-No and Hanano games with various constraints
Owen Crabtree, Valia Mitsou
This work shows new results on the complexity of games Jelly-No and Hanano with various constraints on the size of the board and number of colours. Hanano and Jelly-No are one-play…
Parameterized Spanning Tree Congestion
Michael Lampis, Valia Mitsou, Edouard Nemery +3
In this paper we study the Spanning Tree Congestion problem, where we are given a graph and are asked to find a spanning tree of minimum maximum congestion. Here, the…
Fine-grained Meta-Theorems for Vertex Integrity
Michael Lampis, Valia Mitsou
Vertex Integrity is a graph measure which sits squarely between two more well-studied notions, namely vertex cover and tree-depth, and that has recently gained attention as a struc…
Grundy Distinguishes Treewidth from Pathwidth
Rémy Belmonte, Eun Jung Kim, Michael Lampis +2
Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to und…