TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 17.11.2011

isti-logo

Page Content

to Navigation

On the Computational Complexity of Realizing Degree Sequences as Directed Acyclic Graphs

André Nichterlein (TU Berlin)

We study graph realization problems where a degree sequence is given and the task is to decide whether there is a graph whose vertex degrees match to the given sequence. Realizing a given degree sequence as undirected or directed graph is known to be polynomial-time solvable. In contrary, we show NP-hardness for the problem of realizing a given sequence of pairs of positive integers (representing indegree and outdegree) with a directed acyclic graph, answering an open question of Berger and Müller-Hannemann [FCT 2011]. Furthermore, we classify the problem as fixed-parameter tractable with respect to the maximal degree.

date
speaker
location
language
17.11.2011 16:15
André Nichterlein
FR 6510
german/
english*

* Language is depending on the audience.

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe