Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Orientation of a graph with minimized out-degree #7528

Closed
nathanncohen mannequin opened this issue Nov 25, 2009 · 6 comments
Closed

Orientation of a graph with minimized out-degree #7528

nathanncohen mannequin opened this issue Nov 25, 2009 · 6 comments
Assignees
@rlmill
Labels
c: graph theory p: major / 3 t: enhancement
Milestone
sage-4.3

Comments

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Nov 25, 2009

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 nathanncohen mannequin added this to the sage-4.3.1 milestone Nov 25, 2009
@nathanncohen nathanncohen mannequin assigned rlmill Nov 25, 2009
@nathanncohen

This comment has been minimized.

Sign in to view
@nathanncohen nathanncohen mannequin added the s: needs review label Dec 5, 2009
@nathanncohen nathanncohen mannequin changed the title Orientation of a graph with bounded out-degree Orientation of a graph with minimized out-degree Dec 5, 2009
@rlmill
Copy link
Mannequin

rlmill mannequin commented Dec 15, 2009

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?

@rlmill rlmill mannequin added s: needs info and removed s: needs review labels Dec 15, 2009
@nathanncohen
Copy link
Mannequin Author

nathanncohen mannequin commented Dec 16, 2009

comment:4

Attachment: trac_7528.patch.gz

Indeed ! ( corrected )

@rlmill
Copy link
Mannequin

rlmill mannequin commented Dec 16, 2009

Reviewer: Robert Miller

@rlmill
Copy link
Mannequin

rlmill mannequin commented Dec 16, 2009

Author: Nathann Cohen

@mwhansen
Copy link
Contributor

Merged: sage-4.3.rc1

@mwhansen mwhansen modified the milestones: sage-4.3.1, sage-4.3 Dec 19, 2009
@nathanncohen nathanncohen mannequin mentioned this issue Jun 6, 2010
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@rlmill rlmill

Labels
c: graph theory p: major / 3 t: enhancement
Projects
None yet
Milestone
sage-4.3
Development

No branches or pull requests
1 participant
@mwhansen