5 papers
Cosigning Crossing Families and Outer-Planar Gadgets
Ahmad Abdi, Mahsa Dalirrooyfard, Meike Neuwohner
Let be a crossing family over ground set , that is, for any two sets with nonempty intersection and proper union, both sets are in . Let $…
Approximation Schemes for Planar Graph Connectivity Problems
Meike Neuwohner, Vera Traub, Rico Zenklusen
Finding a smallest subgraph that is k-edge-connected, or augmenting a k-edge-connected graph with a smallest subset of given candidate edges to become (k+1)-edge-connected, are amo…
A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
Meike Neuwohner, Olha Silina, Michael Zlatin
We introduce and study a directed analogue of the weighted Tree Augmentation Problem (WTAP). In the weighted Directed Tree Augmentation Problem (WDTAP), we are given an oriented tr…
A characterization of unimodular hypergraphs with disjoint hyperedges
Marco Caoduro, Meike Neuwohner, Joseph Paat
The incidence matrix of a graph is totally unimodular if and only if the graph is bipartite, i.e., it contains no odd cycles. We extend the characterization of total unimodularity…
Strong orientation of a connected graph for a crossing family
Ahmad Abdi, Mahsa Dalirrooyfard, Meike Neuwohner
Given a connected graph and a crossing family over ground set such that for every , we prove there exists a strong o…