TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 24.05.2018

isti-logo

Page Content

to Navigation

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

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe