Name
Abstract | ||
|---|---|---|
A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11940128_43 | ISAAC |
Keywords | Field | DocType |
transitively orientable,transitive relation,inclusion minimal set,undirected graph,polynomial time,transitive orientation,arbitrary graph,resulting graph,minimal comparability completion,simple algorithm | Strength of a graph,Discrete mathematics,Combinatorics,Comparability graph,Transitive reduction,Cycle graph,Null graph,Semi-symmetric graph,Symmetric graph,Mathematics,Complement graph | Conference |
Volume | ISSN | ISBN |
4288 | 0302-9743 | 3-540-49694-7 |
Citations | PageRank | References |
4 | 0.40 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pinar Heggernes | 1 | 845 | 72.39 |
| Federico Mancini | 2 | 78 | 9.79 |
| Charis Papadopoulos | 3 | 151 | 17.75 |