Abstract | ||
---|---|---|
Suppose that D is an acyclic orientation of the graph G. An arc of D is dependent if its reversal creates a directed cycle. Let d"m"i"n(G) (d"m"a"x(G)) denote the minimum (maximum) of the number of dependent arcs over all acyclic orientations of G. We call Gfully orientable if G has an acyclic orientation with exactly k dependent arcs for every k satisfying d"m"i"n(G)= |
Year | DOI | Venue |
---|---|---|
2010 | 10.1016/j.ejc.2009.03.024 | Eur. J. Comb. |
Keywords | Field | DocType |
full orientability,k dependent arc,gfully orientable,acyclic orientation,dependent arc,graph g.,maximum degree,satisfiability | Graph,Discrete mathematics,Combinatorics,Orientability,Mathematics,Acyclic orientation | Journal |
Volume | Issue | ISSN |
31 | 2 | 0195-6698 |
Citations | PageRank | References |
2 | 0.44 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hsin-Hao Lai | 1 | 13 | 3.19 |
Ko-wei Lih | 2 | 529 | 58.80 |