Digraph 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 graph (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 2 of 2 algorithms

See more
Fulkerson–Chen–Anstee1982O(n)O(n)O(1)O(1)
Kleitman–Wang Algorithm1973O(n)O(n)O(n)O(n)

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table