Inhalt des Dokuments
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.
Back to the research colloquium site.