4 papers
Finding Minimum Distance Preservers: A Parameterized Study
Kirill Simonov, Farehe Soheil, Shaily Verma
For a given graph and a subset of vertices , a \emph{distance preserver} is a subgraph of that preserves shortest paths between the vertices of . We distinguish betwe…
Parameterized Complexity of Vehicle Routing
Michelle Döring, Jan Fehse, Tobias Friedrich +6
The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph ,…
Connected Partitions via Connected Dominating Sets
Aikaterini Niklanovits, Kirill Simonov, Shaily Verma +1
The classical theorem due to Győri and Lovász states that any -connected graph admits a partition into connected subgraphs, where each subgraph has a prescribed size and…
A Parameterized Study of Secluded Structures in Directed Graphs
Jonas Schmidt, Shaily Verma, Nadym Mallek
Given an undirected graph and an integer , the Secluded -Subgraph problem asks you to find a maximum size induced subgraph that satisfies a property and has at most $…