Orientation of a graph with minimized out-degree

[nathanncohen]

The function minimum_outdegree_orientation() returns a DiGraph which is an orientation of the current graph, such that the maximum out-degree is minimized.

Uses LP !

Nathann

Component: graph theory

Author: Nathann Cohen

Reviewer: Robert Miller

Merged: sage-4.3.rc1

Issue created by migration from https://trac.sagemath.org/ticket/7528

[nathanncohen]

Description changed:

--- 
+++ 
@@ -1 +1,5 @@
-Given an undirected graph and an integer k, it is possible to find through the flow algorithm an orientation of it such that any vertex has an out-degree of at most k ( or say that this is impossible )
+The function minimum_outdegree_orientation() returns a DiGraph which is an orientation of the current graph, such that the maximum out-degree is minimized.
+
+Uses LP !
+
+Nathann

[rlmill]

comment:3

I'm ready to give this a positive review, except there is a conflict:

Given a complete bipartite graph `K_{n,m}`, the minimum  
outdegree of an orientation is  
`\left\lceil \frac {nm} {n+m}\right\rceil`:: 

sage: g = graphs.CompleteBipartiteGraph(3,4) 
sage: o = g.minimum_outdegree_orientation() # optional - requires GLPK or CBC 
sage: max(o.out_degree()) == ceil((4*3)/(3+4)) # optional - requires GLPK or CBC 
True

Should "the minimum outdegree" be "the smallest possible maximum outdegree", or something similar?

[nathanncohen]

comment:4

Attachment: trac_7528.patch.gz

Indeed ! ( corrected )

[rlmill]

Reviewer: Robert Miller