Opened 18 months ago
Closed 11 months ago
#28243 closed enhancement (fixed)
Accelerate `is_cactus()`
Reported by: | gh-r-barnes | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-9.1 |
Component: | graph theory | Keywords: | cactus |
Cc: | Merged in: | ||
Authors: | João Tavares | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | ac1cf88 (Commits) | Commit: | ac1cf884ade760e719e48a5c44461e7065370c9a |
Dependencies: | Stopgaps: |
Description
This proof could be used to accelerate is_cactus()
by providing a quick O(1) check that can detect a large class of graphs which are not cactuses. This, in turn, would be helpful for situations where is_cactus()
is applied to large graphs.
Change History (11)
comment:1 Changed 18 months ago by
comment:2 Changed 18 months ago by
- Component changed from group theory to graph theory
If you are not able to double check the proof, it's better to find a reference (article, school book, etc.). This looks like a class exercise...
comment:3 Changed 18 months ago by
Actually, fill free to add the test without reference. This result is well known and often used as an exercise. Furthermore, this is a tight bound and we have graphs reaching it.
sage: for n in range(1, 10): ....: G = graphs.FriendshipGraph(n) ....: G.size() == 3 * (G.order() - 1) / 2 ....: True True True True True True True True True sage: for _ in range(10): ....: G = graphs.RandomBlockGraph(10, 3) ....: G.size() == 3 * (G.order() - 1) / 2 ....: True True True True True True True True True True
comment:4 Changed 13 months ago by
- Milestone changed from sage-8.9 to sage-9.1
Ticket retargeted after milestone closed
comment:5 Changed 11 months ago by
- Branch set to u/gh-tabus/accelerate__is_cactus___
comment:6 Changed 11 months ago by
- Commit set to ac1cf884ade760e719e48a5c44461e7065370c9a
- Status changed from new to needs_review
New commits:
ac1cf88 | Added the necessary condition check
|
comment:7 Changed 11 months ago by
- Reviewers set to David Coudert
Please add your full name in the field Authors
of this page.
comment:8 follow-up: ↓ 9 Changed 11 months ago by
comment:9 in reply to: ↑ 8 Changed 11 months ago by
Replying to gh-tabus: Here it is. Is there anything else that should be done?
comment:10 Changed 11 months ago by
- Status changed from needs_review to positive_review
For this simple test, this is enough.
comment:11 Changed 11 months ago by
- Branch changed from u/gh-tabus/accelerate__is_cactus___ to ac1cf884ade760e719e48a5c44461e7065370c9a
- Resolution set to fixed
- Status changed from positive_review to closed
(I have not yet found an academic citation for the theorem.)