Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Parameterized Complexity of Edge-Constrained Graph Partitioning
Ajinkya Gaikwad, Jan Pokorný, Tomáš Valla
We study the Edge-Constrained Graph Partitioning Problem (ECGP), which asks whether the vertices of a graph can be partitioned into r parts, each inducing at least gamma edges. We…
cs.DS2025
Pathfinding in Self-Deleting Graphs
Michal Dvořák, Dušan Knop, Michal Opler +3
In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices. In particular, we st…
cs.DS2024
Equitable Connected Partition and Structural Parameters Revisited: N-fold Beats Lenstra
Václav Blažej, Dušan Knop, Jan Pokorný +1
We study the Equitable Connected Partition (ECP for short) problem, where we are given a graph G=(V,E) together with an integer p, and our goal is to find a partition of V into p p…