#7528: Orientation of a graph with minimized out-degree
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: rlm
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-4.3.1
Component: graph theory | Keywords:
Work_issues: | Author:
Upstream: N/A | Reviewer:
Merged: |
----------------------------+-----------------------------------------------
Changes (by rlm):
* status: needs_review => needs_info
Comment:
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?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7528#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
