1 citations · 1 across the 13 of their papers we have counts for
6 papers · 1 filter
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…
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…
Parameterized Critical Node Cut Revisited
Dušan Knop, Nikolaos Melissinos, Manolis Vasilakis
We study how to sparsify connectivity in graphs under a tight deletion budget. Given a graph and integers , Critical Node Cut (CNC) asks whether we can delete at mos…
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 ,…
Exact Algorithms for Distance to Unique Vertex Cover
Foivos Fioravantes, Dušan Knop, Nikolaos Melissinos +2
Horiyama et al. (AAAI 2024) studied the problem of generating graph instances that possess a unique minimum vertex cover under specific conditions. Their approach involved pre-assi…
Structural Parameterizations for Induced and Acyclic Matching
Michael Lampis, Manolis Vasilakis
We revisit the (structurally) parameterized complexity of Induced Matching and Acyclic Matching, two problems where we seek to find a maximum independent set of edges whose endpoin…