#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 gh-r-barnes

(I have not yet found an academic citation for the theorem.)

comment:2 Changed 18 months ago by dcoudert

  • 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 dcoudert

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 embray

  • Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

comment:5 Changed 11 months ago by gh-tabus

  • Branch set to u/gh-tabus/accelerate__is_cactus___

comment:6 Changed 11 months ago by gh-tabus

  • Commit set to ac1cf884ade760e719e48a5c44461e7065370c9a
  • Status changed from new to needs_review

New commits:

ac1cf88Added the necessary condition check

comment:7 Changed 11 months ago by dcoudert

  • Reviewers set to David Coudert

Please add your full name in the field Authors of this page.

comment:8 follow-up: Changed 11 months ago by gh-tabus

  • Authors set to João Tavares

comment:9 in reply to: ↑ 8 Changed 11 months ago by gh-tabus

Replying to gh-tabus: Here it is. Is there anything else that should be done?

comment:10 Changed 11 months ago by dcoudert

  • Status changed from needs_review to positive_review

For this simple test, this is enough.

comment:11 Changed 11 months ago by vbraun

  • Branch changed from u/gh-tabus/accelerate__is_cactus___ to ac1cf884ade760e719e48a5c44461e7065370c9a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.