10 citations · 11 across the 18 of their papers we have counts for
8 papers · 1 filter
Continuous Computational Social Choice: A Case Study in Bribery
Martin Koutecký, Nikolaos Melissinos, Tung Anh Vu +1
Computational social choice seeks algorithmic answers to questions about preference aggregation, safety of elections, robustness of outcomes, stability, etc. It overwhelmingly mode…
Solving Multiagent Path Finding on Highly Centralized Networks
Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan +3
The Mutliagent Path Finding (MAPF) problem consists of identifying the trajectories that a set of agents should follow inside a given network in order to reach their desired destin…
Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan +2
Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position while avoiding collisions. By optimal, we mean…
Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology
Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan +2
In the Multiagent Path Finding problem (MAPF for short), we focus on efficiently finding non-colliding paths for a set of agents on a given graph , where each agent seeks a…
Parameterised distance to local irregularity
Foivos Fioravantes, Nikolaos Melissinos, Theofilos Triommatis
A graph is \emph{locally irregular} if no two of its adjacent vertices have the same degree. In [Fioravantes et al. Complexity of finding maximum locally irregular induced subg…
Filling Crosswords is Very Hard
Laurent Gourvès, Ararat Harutyunyan, Michael Lampis +1
We revisit a classical crossword filling puzzle which already appeared in Garey\&Jonhson's book. We are given a grid with vertical and horizontal slots and a dictionary with $m…
Digraph Coloring and Distance to Acyclicity
Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos
In -Digraph Coloring we are given a digraph and are asked to partition its vertices into at most sets, so that each set induces a DAG. This well-known problem is NP-hard, as…
(In)approximability of Maximum Minimal FVS
Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei +2
We study the approximability of the NP-complete \textsc{Maximum Minimal Feedback Vertex Set} problem. Informally, this natural problem seems to lie in an intermediate space between…