From the 1 of 8 linked papers with an AI index.
8 papers
Finite Pinwheel Covering
Sotiris Kanellopoulos
The paper introduces the finite version of the Pinwheel Covering problem, called k-Visits Covering, and proves it is strongly NP‑complete even for k=2, while also providing efficie…
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…
Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
Sotiris Kanellopoulos, Giorgos Mitropoulos, Christos Pergaminelis +1
The k-Visits problem is a recently introduced finite version of Pinwheel Scheduling [Kanellopoulos et al., SODA 2026]. Given the deadlines of n tasks, the problem asks whether ther…
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…
Finite Pinwheel Scheduling: the k-Visits Problem
Sotiris Kanellopoulos, Christos Pergaminelis, Maria Kokkou +2
Pinwheel Scheduling is a fundamental scheduling problem, in which each task is associated with a positive integer , and the objective is to schedule one task per time slot…
Beer Path Problems in Temporal Graphs
Andrea D'Ascenzo, Giuseppe F. Italiano, Sotiris Kanellopoulos +3
Computing paths in graph structures is a fundamental operation in a wide range of applications, from transportation networks to data analysis. The beer path problem, which captures…