Establishes NP-hardness of MAPF on trees for labeled and 2-colored variants across three objectives by proving hardness of stack rearrangement, which reduces to motion on subdivided stars.
Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity , booktitle =
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
verdicts
UNVERDICTED 2representative citing papers
Gives poly-time algorithms for MINSUM capacity augmentation to ensure strong stability in HR with ties, proves NP-hardness for MINMAX, and bounded-increase results when ties are short.
citing papers explorer
-
On the Hardness of Optimal Motion on Trees
Establishes NP-hardness of MAPF on trees for labeled and 2-colored variants across three objectives by proving hardness of stack rearrangement, which reduces to motion on subdivided stars.
-
Optimal Capacity Modification for Stable Matchings with Ties
Gives poly-time algorithms for MINSUM capacity augmentation to ensure strong stability in HR with ties, proves NP-hardness for MINMAX, and bounded-increase results when ties are short.