direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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.

17.11.2011 16:15
André Nichterlein
FR 6510

* Language is depending on the audience.

Back to the research colloquium site.

Zusatzinformationen / Extras