9 citations · 20 across the 5 of their papers we have counts for
3 papers · 1 filter
Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
François Dross, Krzysztof Fleszar, Karol Węgrzycki +1
In this paper, we study problems of connecting classes of points via noncrossing structures. Given a set of colored terminal points, we want to find a graph for each color that con…
A PTAS for Euclidean TSP with Hyperplane Neighborhoods
Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma +1
In the Traveling Salesperson Problem with Neighborhoods (TSPN), we are given a collection of geometric regions in some space. The goal is to output a tour of minimum length that vi…
New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness
Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase
We study the classical NP-hard problems of finding maximum-size subsets from given sets of terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint p…