Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An algorithm for generating all maximal independent subsets of posets

Ein Algorithmus zur Bestimmung aller maximal unabhängigen Mengen einer Ordnung

  • Published:
Computing Aims and scope Submit manuscript

Abstract

This paper gives an algorithm for determining the setU 0(Θ) of all maximal independent subsets of a finite poset Θ=(A, O), based on a (complex) Θ-induced arrangement ofU 0(Θ) as a rooted tree. By this procedure, all essential data manipulations can be restricted to certain bipartite graphs, thereby leading to a computation complexity not exceedingO(|A|·|\(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{O} \)) per maximal independent subset obtained (where\(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{O} \) denotes the immediate ordering relations). In fact, an intensive study of examples (with |A| ranging from 10–200) even showed almost total independence of external parameters such as |A|, |O| or |\(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{O} \)| and at the same time led to considerably low computation times. Thus, in particular, the application of standard graph-theoretical methods to the associated comparability graph of Θ would no longer seem a reasonable approach to the considered problem.

Zusammenfassung

Es wird ein Algorithmus entwickelt, welcher das SystemU 0(Θ) aller unabhängigen Mengen einer endlichen Ordnung Θ=(A, O) generiert, und zwar aufbauend auf einer (komplizierten) Darstellung vonU 0(Θ) als Wurzelbaum. Hierbei können alle wesentlichen Datenmanipulationen innerhalb zugehöriger bipartiter Graphen durchgeführt werden, woraus eine Komplexität von höchstensO(|A|·|\(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{O} \)) pro gefundener maximal unabhängiger Menge resultiert (\(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{O} \) bezeichnet die unmittelbaren Ordnungs-relationen). Tatsächlich zeigte eine intensive Untersuchung von Beispielen mit Trägermengen der Kardinalität 10 bis 200 nahezu überhaupt keine Abhängigkeit der durchschnittlichen Rechenzeit von externen Parametern (wie |A|, |O| und |\(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{O} \)|). Zudem ergaben sich erstaunlich niedrige Rechenzeiten. Insgesamt erweist sich somit der Algorithmus als empfehlenswerte Alternative gegenüber der Anwendung der bekannten graphentheoretischen Verfahren auf den zu Θ gehörenden Vergleichbarkeitsgraphen.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Aho, A. V., Hopcraft, J. E., Ullmann, J. D.: The design and analysis of computer algorithms. Reading, Mass.: Addison-Wesley 1974.

    Google Scholar 

  2. Berge, C.: Principles of combinatorics. London: Academic Press 1971.

    Google Scholar 

  3. Bollobas, B.: Graph theory. (Graduate texts in Mathematics, Vol. 63.) New York: Springer 1979.

    Google Scholar 

  4. Bollobas, B., Erdös, P.: Cliques in random graphs. Math. Proc. Camb. Phil. Soc.80, 419–427 (1976).

    Google Scholar 

  5. Bron, C., Kerbosch, J.: Algorithm 457, Finding all cliques of an undirected graph. Comm. ACM16, 575–577 (1973).

    Google Scholar 

  6. Buer, H., Möhring, R. H.: A fast algorithm for the decomposition of graphs and acyclic networks (extended abstract). Forthcoming in Oper. Res. Verfahren37, 259–263 (1980).

    Google Scholar 

  7. Dilworth, R. P.: Some combinatorial problems on partially ordered sets in “Combinatorial Analysis”. Proc. Symp. Appl. Math., Vol. 10, pp. 85–90. Providence, R. I.: American Mathematical Society 1960.

    Google Scholar 

  8. Even, S., Pnueli, A., Lempel, A.: Permutation graphs and transitive graphs. J. of the Ass. f. Comp. Mach.19, 400–410 (1972).

    Google Scholar 

  9. Gerhards, L., Lindenberg, W.: Clique detection for nondirected graphs: Two new algorithms. Computing21, 295–322 (1979).

    Google Scholar 

  10. Gilmore, P. C., Hoffmann, A. J.: A characterization of comparability graphs and of interval graphs. Can. J. Math.16, 539–548 (1964).

    Google Scholar 

  11. Golumbic, M. C.: Comparability graphs and a new matroid. J. of comb. Theory (B)22, 68–90 (1977).

    Google Scholar 

  12. Golumbic, M. C.: The complexity of comparability graph recognition and coloring. Computing18, 199–208 (1977).

    Google Scholar 

  13. Gorenstein, S.: An algorithm for project (Job) sequencing with resource constraints. Operations Research20, 4 (1972).

    Google Scholar 

  14. Kaerkes, R.: Netzplan-Theorie. Operations-Research-Verfahren27, 1–65 (1976).

    Google Scholar 

  15. Lawler, E. L.: Combinatorial optimization: Networks and matroids. New York: Holt, Rinehart and Winston 1976.

    Google Scholar 

  16. Mirsky, L.: A dual of Dilworth's decomposition theorem. Amer. Math. Monthly78, 876–877 (1971).

    Google Scholar 

  17. Radermacher, F. J.: Kapazitätsoptimierung in Netzplänen. (Mathematical Systems in Economics, Band 40.) Meisenheim am Glan: Verlag Anton Hain 1978.

    Google Scholar 

  18. Tsukiyama, S., Ide, H., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. Siam J. Comput.6, 505–517 (1977).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Lehrstuhl für Mathematik Fachrichtung Operations Research, Technische Hochschule Aachen, Templergraben 64/3, D-5100, Aachen, Federal Republic of Germany

    M. Bartusch

Authors
  1. M. Bartusch
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This paper was supported by the Minister für Wissenschaft und Forschung des Landes NRW, Federal Republic of Germany.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bartusch, M. An algorithm for generating all maximal independent subsets of posets. Computing 26, 343–354 (1981). https://doi.org/10.1007/BF02237953

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02237953

Key words

Search

Navigation