Opened 4 years ago
Last modified 3 years ago
#18869 new enhancement
add more versions of Lovasz theta for graphs
Reported by: | dimpase | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.5 |
Component: | graph theory | Keywords: | |
Cc: | krishnaniyer97@… | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
There are variations by Schrijver and Szegedy of Lovasz theta which are computable using SDP, just as the one from #18830.
An implementation calling the standard in Sage SDP solver from cvxopt
is available as a gist by Dan Stahlke, who kindly gave us permission to include parts of it into Sage under GPL.
See
Szegedy, M., “ A note on the number of Lovasz and the generalized Delsarte bound”, In proceedings of 35th Annual Symposium on Foundations of Computer Science, 36–39 (1994)
for the corresponding definitions.
Change History (3)
comment:1 Changed 3 years ago by
- Cc ncohen removed
- Milestone changed from sage-6.8 to sage-7.5
comment:2 Changed 3 years ago by
- Cc krishnaniyer97@… added
comment:3 Changed 3 years ago by
- Description modified (diff)
Note: See
TracTickets for help on using
tickets.