6 papers
Temporal Path Covers: Dilworth Properties and Parameterized Complexity
Lapo Cioni, Sotiris Kanellopoulos, Edouard Nemery +3
The Minimum Temporal Path Cover (TPC) and Minimum Temporally Disjoint Path Cover (TDPC) problems were introduced by [Chakraborty, Dailly, Foucaud, Klasing, MFCS '24]. Both were sho…
EF(X) Orientations: A Parameterized Complexity Perspective
Sotiris Kanellopoulos, Edouard Nemery, Christos Pergaminelis +2
The concept of fair orientations in graphs was introduced by Christodoulou, Fiat, Koutsoupias, and Sgouritsa in 2023, naturally modeling fair division scenarios in which resources…
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…
On the parameterized complexity of Broadcast Independence and Broadcast Packing
Joanne Dumont, Edouard Nemery, Anthony Perez +1
A broadcast on a connected graph is a function f that assigns each vertex v an integer f(v) with 0 <= f(v) <= ecc(v) where ecc(v) denotes the eccentricity of v. A vertex u hears a…
Structural Parameters for Steiner Orientation
Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos +3
We consider the \textsc{Steiner Orientation} problem, where we are given as input a mixed graph and a set of demand pairs , . The goal is to ori…
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 ,…