direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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. [1]

To top

------ Links: ------

Zusatzinformationen / Extras