DAG Realization Problem

Given a sequence S:=(a1,b1),,(an,bn)S := (a_1, b_1), \ldots, (a_n, b_n) with ai,biZ0+a_i, b_i \in \mathbb{Z}_0^+, does there exist a directed acyclic graph (DAG) (no parallel arcs allowed) with labeled vertex set V:={v1,,vn}V := \{v_1, \ldots , v_n\} such that for all viVv_i \in V indegree and outdegree of viv_i match exactly the given numbers aia_i and bib_i, respectively

Parameters

  • nn: number of degree pairs

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 1 of 1 algorithms

See more
Berger & Müller-Hannemann2011O(exp(n))O(\exp(n))

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table