direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

Zusatzinformationen / Extras