5 citations · 6 across the 3 of their papers we have counts for
7 papers
Reconfiguration of Digraph Homomorphisms
Benjamin Lévêque, Moritz Mühlenthaler, Thomas Suzan
For a fixed graph H, the H-Recoloring problem asks whether for two given homomorphisms from a graph G to H, we can transform one into the other by changing the image of a single ve…
Fixed-Parameter Algorithms for Graph Constraint Logic
Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito +3
Non-deterministic constraint logic (NCL) is a simple model of computation based on orientations of a constraint graph with edge weights and vertex demands. NCL captures \PSPACE\xsp…
Fault-Tolerant Edge-Disjoint Paths -- Beyond Uniform Faults
David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler +1
The overwhelming majority of survivable (fault-tolerant) network design models assume a uniform fault model. Such a model assumes that every subset of the network resources (edges…
Flexible Graph Connectivity: Approximating Network Design Problems Between 1- and 2-connectivity
David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler
Graph connectivity and network design problems are among the most fundamental problems in combinatorial optimization. The minimum spanning tree problem, the two edge-connected span…
Shortest Reconfiguration of Matchings
Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito +1
Imagine that unlabelled tokens are placed on the edges of a graph, such that no two tokens are placed on incident edges. A token can jump to another edge if the edges having tokens…
How to Secure Matchings Against Edge Failures
Felix Hommelsheim, Moritz Mühlenthaler, Oliver Schaudt
Suppose we are given a bipartite graph that admits a perfect matching and an adversary may delete any edge from the graph with the intention of destroying all perfect matchings. We…