Opened 11 years ago
Closed 11 years ago
#7528 closed enhancement (fixed)
Orientation of a graph with minimized out-degree
| Reported by: | ncohen | Owned by: | rlm |
|---|---|---|---|
| Priority: | major | Milestone: | sage-4.3 |
| Component: | graph theory | Keywords: | |
| Cc: | Merged in: | sage-4.3.rc1 | |
| Authors: | Nathann Cohen | Reviewers: | Robert Miller |
| Report Upstream: | N/A | Work issues: | |
| Branch: | Commit: | ||
| Dependencies: | Stopgaps: |
Description (last modified by )
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
Attachments (1)
Change History (7)
comment:1 Changed 11 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
- Summary changed from Orientation of a graph with bounded out-degree to Orientation of a graph with minimized out-degree
comment:3 Changed 11 years ago by
- Status changed from needs_review to needs_info
Changed 11 years ago by
comment:4 Changed 11 years ago by
- Status changed from needs_info to needs_review
Indeed ! ( corrected )
comment:5 Changed 11 years ago by
- Reviewers set to Robert Miller
- Status changed from needs_review to positive_review
comment:6 Changed 11 years ago by
- Merged in set to sage-4.3.rc1
- Milestone changed from sage-4.3.1 to sage-4.3
- Resolution set to fixed
- Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
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 TrueShould "the minimum outdegree" be "the smallest possible maximum outdegree", or something similar?