4 papers
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…
Density of Traceable Graphs
Michal DvoÅák, DuÅ¡an Knop, Michal Opler +3
We establish tight lower and upper bounds on the number of edges in traceable graphs in several classes of dense graphs. A graph is traceable if it has a Hamiltonian path. We show…
Practical approach to -Euclidean Preferences
Michal DvoÅák, DuÅ¡an Knop, Jan Pokorný +1
An election is a pair of candidates and voters. Each vote is a ranking (permutation) of the candidates. An election is -Euclidean if there is an embedding of both candid…
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…