5 papers
An FPT Algorithm for Diverse Minimum s-t Cuts
Krishnan Dehaleesan, Pål Grønås Drange, Fedor V. Fomin +2
We study the problem of finding a family of diverse minimum edge s-t cuts in a directed weighted graph G. Given integers k and d, the task is to decide whether G contains k minimum…
Identification to Subclasses of Chordal Graphs
Petr A. Golovach, Laure Morelle, Daniël Paulusma
An identification of two vertices and in a graph replaces them with a new vertex whose neighborhood is the union of the neighborhoods of and . We study the {\sc ${\c…
H-Planarity and Parametric Extensions: when Modulators Act Globally
Fedor V. Fomin, Petr A. Golovach, Laure Morelle +1
We introduce a series of graph decompositions based on the modulator/target scheme of modification problems that enable several algorithmic applications that parametrically extend…
Fault-Tolerant Matroid Bases
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +1
We investigate the problem of constructing fault-tolerant bases in matroids. Given a matroid M and a redundancy parameter k, a k-fault-tolerant basis is a minimum-size set of eleme…
When does FTP become FPT?
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +1
In the problem Fault-Tolerant Path (FTP), we are given an edge-weighted directed graph G = (V, E), a subset U \subseteq E of vulnerable edges, two vertices s, t \in V, and integers…