0
$\begingroup$

what is the algorithm for enumerating all maximal independent set on trees (without the constaint of lexicographic order) . It 's very natural to find an algorithm faster than $ O(3^{n/3})$ on trees .

In fact ,in trees we have at most $O(2^{n/2})$ maximal independent set but I try to find an algorithm to enumerate those .

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ The algorithm? Which one? What have you tried, and where did you get stuck? $\endgroup$
    – Raphael
    May 21, 2015 at 16:05
  • $\begingroup$ The number of MIS in tree is at most $ 2^{n/2} $ . So I try to find an algorithm to compute all MIS in a faster time that the general algorithm with running time $O(3^{n/3})$. I think we can have an algorithm to enumerate all MIS on tree with only a running time $O(2^{n/2})$ $\endgroup$
    – tounsy
    May 21, 2015 at 16:24
  • $\begingroup$ We have an algorithm in polynomial delay ( Y. H. Chang, Jia-Shung Wang, Richard C. T. Lee: Generating All Maximal Independent Sets on Trees in Lexicographic Order. Inf. Sci. 76(3-4): 279-296 (1994) . But I don't need the lexicographic order . I need an algorithm generating all maximal independent sets on trees without the constraint of lexicographic order $\endgroup$
    – tounsy
    May 21, 2015 at 16:30
  • 1
    $\begingroup$ Please edit the question to incorporate all requested information. Don't just leave information in the comments -- the comments exist only to help you improve your question, and can disappear at any time. People shouldn't need to read the question to understand your question. $\endgroup$
    – D.W. ♦
    May 22, 2015 at 15:27
  • $\begingroup$ @TomvanderZanden Ah, my bad. I'll remove the statement. (Still, I think "at most" implies a "$\leq$" which an $O$ can never give, due to the constant factor, and because the bound may not be tight. The language feels imprecise as a consequence.) $\endgroup$
    – Raphael
    May 25, 2015 at 10:52

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.