Name
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(D) denote the number of dependent arcs in D. Define d"m"i"n(G) (d"m"a"x(G)) to be the minimum (maximum) number of d(D) over all acyclic orientations D of G. We call G fully orientable if G has an acyclic orientation with exactly k dependent arcs for every k satisfying d"m"i"n(G)= |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.ipl.2007.08.020 | Inf. Process. Lett. |
Keywords | Field | DocType |
triangle- free graph,cover graph,k dependent arc,acyclic orientation,dependent arc,acyclic orientations d,2-degenerate graph,graph g.,triangle free graph,satisfiability | Degenerate energy levels,Discrete mathematics,Graph algorithms,Graph,Combinatorics,Orientability,Directed acyclic graph,Mathematics,Triangle-free graph,Acyclic orientation | Journal |
Volume | Issue | ISSN |
105 | 5 | 0020-0190 |
Citations | PageRank | References |
5 | 0.55 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hsin-Hao Lai | 1 | 13 | 3.19 |
| Gerard J. Chang | 2 | 1163 | 112.81 |
| Ko-wei Lih | 3 | 529 | 58.80 |