Sie sind hier

# Finding Disjoint Connecting Subgraphs in Surface-embedded Graphs

Malte Renken (TU Berlin)

Given a graph $G$, a set $T \subseteq V(G)$ of terminal vertices and a partition of $T$ into blocks, the problem "Disjoint Connecting Subgraphs" is to find a set of vertex-disjoint subgraphs of $G$, each covering exactly one block.
While NP-hard in general, Robertson and Seymour showed that the problem is solvable in polynomial time for any fixed size of $T$. Generalizing a result of Reed, we give an $O(n \log(n))$ algorithm when $G$ is embedded into an arbitrary but fixed surface.

Date
Speaker
Location
Language
24.05.2018
16:15
Malte Renken
TEL 512
English

Back to the research colloquium site.

To top