5 citations · 6 across the 5 of their papers we have counts for
9 papers
A Complexity Dichotomy for Generalized Rainbow Matchings Based on Color Classes
Felix Hommelsheim, Pia Jehmlich, Moritz Mühlenthaler
Given an edge-colored graph, the Maximum Rainbow Matching problem asks for a maximum-cardinality matching of the graph that contains at most one edge from each color. We provide th…
Reconfiguring homomorphisms to reflexive graphs via a simple reduction
Moritz Mühlenthaler, Mark H. Siggers, Thomas Suzan
Given a graph and two graph homomorphisms and from to a fixed graph , the problem -Recoloring asks whether there is a transformation from to that chan…
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…
On the Connectedness of Clash-free Timetables
Moritz Mühlenthaler, Rolf Wanka
We investigate the connectedness of clash-free timetables with respect to the Kempe-exchange operation. This investigation is related to the connectedness of the search space of ti…