19 citations · 61 across the 20 of their papers we have counts for
6 papers · 1 filter
Almost Disjoint Paths and Separating by Forbidden Pairs
Oliver Bachtler, Tim Bergner, Sven O. Krumke
By Menger's theorem the maximum number of arc-disjoint paths from a vertex s to a vertex t in a directed graph equals the minumum number of arcs needed to disconnect s and t, i.e.,…
On the Bicriterion Maximum Flow Network Interdiction Problem
Luca E. Schäfer, Stefan Ruzika, Sven O. Krumke +1
This article focuses on a biobjective extension of the maximum flow network interdiction problem, where each arc in the network is associated with two capacity values. Two maximum…
Towards obtaining a 3-Decomposition from a perfect Matching
Oliver Bachtler, Sven O. Krumke
A decomposition of a graph is a set of subgraphs whose edges partition those of . The 3-decomposition conjecture posed by Hoffmann-Ostenhof in 2011 states that every connected c…
On the Mixed Connectivity Conjecture of Beineke and Harary
Sebastian S. Johann, Sven O. Krumke, Manuel Streicher
The conjecture of Beineke and Harary states that for any two vertices which can be separated by vertices and edges for but neither by vertices and edges…
Simultaneously Dominating all Spanning Trees of a Graph
Sebastian S. Johann, Sven O. Krumke, Manuel Streicher
We investigate the problem of simultaneously dominating all spanning trees of a given graph. We prove that on 2-connected graphs, a subset of the vertices dominates all spanning tr…
Minimum Cycle Decomposition: A Constructive Characterization for Graphs of Treewidth Two with Node Degrees Two and Four
Irene Heinrich, Sven O. Krumke
Substantial efforts have been made to compute or estimate the minimum number of cycles needed to partition the edges of an Eulerian graph. We give an equivalent characteriza…