TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 26.04.2012


Page Content

to Navigation

An Advanced Search Tree Algorithm For Two-Layer Planarization

Mathias Weller (Ph.D. Student TU Berlin)

Given an undirected graph G and an integer k, the NP-hard Two-Layer Planarization problem asks whether G can be transformed into a forest of caterpillar trees by removing at most k edges. Since transforming G into a forest of caterpillar trees requires breaking every cycle, the size f of a minimum feedback edge set is a natural parameter with f ≤ k. We augment previous results for this parameter by presenting an adaptation of Sudermans O(3.562k·poly(n))-time algorithm. Our algorithm runs in O(4.34455f·poly(n)) time, thus improving the previous O(6f·poly(n))-time algorithm. Our algorithm could also serve as a case study for a potential novel two-dimensional branching analysis, working orthogonally to the popular measure and conquer method.

26.04.2012 16:15
Mathias Weller
FR 6510

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe