Loading...
Please wait, while we are loading the content...
Similar Documents
Np-hardness and fixed-parameter tractability of realizing degree sequences with directed acyclic graphs.
| Content Provider | CiteSeerX |
|---|---|
| Author | Nichterlein, André Realization, Dag |
| Abstract | In graph realization problems one is given a degree sequence and the task is to decide whether there is a graph whose vertex degrees match to the given sequence. This realization problem is known to be polynomialtime solvable when the graph is directed or undirected. In contrary, we show NP-completeness for the problem of realizing a given sequence of pairs of positive integers (representing indegrees and outdegrees) with a directed acyclic graph, answering an open question of Berger and Müller-Hannemann [FCT 2011]. Furthermore, we classify the problem as fixedparameter tractable with respect to the parameter “maximum degree”. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Directed Acyclic Graph Realizing Degree Sequence Fixed-parameter Tractability Degree Sequence Positive Integer Parameter Maximum Degree Ller-hannemann Fct Open Question Graph Realization Problem Realization Problem |
| Content Type | Text |