Meike Neuwohner

collaborators

3 papers

math.CO2024

Strong orientation of a connected graph for a crossing family

Ahmad Abdi, Mahsa Dalirrooyfard, Meike Neuwohner

Given a connected graph $G = (V, E)$ and a crossing family $C$ over ground set $V$ such that $∣ δ_{G} (U) ∣ \geq 2$ for every $U \in C$ , we prove there exists a strong or…

cs.DS2024

A $\frac{4}{3}$ -Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs

Meike Neuwohner

The Maximum Leaf Spanning Arborescence problem (MLSA) is defined as follows: Given a directed graph $G$ and a vertex $r \in V (G)$ from which every other vertex is reachable, find a…

cs.DS2023

The $2$ - $3$ -Set Packing problem and a $\frac{4}{3}$ -approximation for the Maximum Leaf Spanning Arborescence problem in rooted dags

Meike Neuwohner

The weighted $3$ -Set Packing problem is defined as follows: As input, we are given a collection $S$ of sets, each of cardinality at most $3$ and equipped with a positive…

Strong orientation of a connected graph for a crossing family

A 34​-Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs

The 2-3-Set Packing problem and a 34​-approximation for the Maximum Leaf Spanning Arborescence problem in rooted dags

A $\frac{4}{3}$ -Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs

The $2$ - $3$ -Set Packing problem and a $\frac{4}{3}$ -approximation for the Maximum Leaf Spanning Arborescence problem in rooted dags