TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 17.11.2011

isti-logo

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

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

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe