#13223: Implement Poset.is_graded using a polynomial time (linear?) algorithm.
-------------------------------------+-------------------------------------
Reporter: nthiery | Owner: sage-combinat
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: sd40 | Merged in:
Authors: Jori Mäntysalo | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jmantysalo/implement_poset_is_graded_using_a_polynomial_time__linear___algorithm_|
a9896c7e9f9e8e6c6f52a25a3370c2d595e2fecf
Dependencies: #13222 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by ncohen):
Yooooooo !
> Yep. Should this one be marked as positive_review and moved to wontfix-
milestone?
+1 to that
> I made a code that was slightly faster when calculating how many of
`Posets(8)` are graded (assuming that ranks were not already computed). IF
"going up" is cheaper than going down, i.e. poset is internally saved as
digraph of upper covers, then in principle current implementation would be
`O(n^2)` and my implementation `O(n)`. But in reality this sppedup is not
happening.
Well, going up or down should be the same cost. The edges are stored twice
(in each direction) in digraphs.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/13223#comment:19>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
