REPOZYTORIUM UNIWERSYTETU
W BIAŁYMSTOKU
UwB

  1. Repozytorium Uniwersytetu w Białymstoku
  2. Czasopisma naukowe / Journals
  3. Formalized Mathematics
  4. Formalized Mathematics, 2006, Volume 14, Issue 4

Szukanie zaawansowane
  • Zespoły i Kolekcje


  • Zaloguj się
  • Zarejestruj się
  • Mój RUB
  • FAQ
  • Polityka
  • Regulamin
  • DOI
  • Instrukcja
  • Aspekty prawne
  • Open Access
  • Archiwum


  • Kontakt
  • O Dspace
  • Strona Biblioteki
  • Strona Uczelni



    • Proszę używać tego identyfikatora do cytowań lub wstaw link do tej pozycji: http://hdl.handle.net/11320/21433
    Pełny rekord metadanych
    Pole DCWartośćJęzyk
    dc.contributor.authorArneson, Broderick-
    dc.contributor.authorRudnicki, Piotr-
    dc.date.accessioned2026-11-05T08:52:32Z-
    dc.date.available2026-11-05T08:52:32Z-
    dc.date.issued2006-
    dc.identifier.citationFormalized Mathematics, Volume 14, Issue 4, Pages 187-206pl
    dc.identifier.issn1426-2630-
    dc.identifier.urihttp://hdl.handle.net/11320/21433-
    dc.description.abstractWe are formalizing the algorithm for recognizing chordal graphs by lexicographic breadth- rst search as presented in [13, Section 3 of Chapter 4, pp. 81-84]. Then we follow with a formalization of another algorithm serving the same end but based on maximum cardinality search as presented by Tarjan and Yannakakis [25]. This work is a part of the MSc work of the fi rst author under supervision of the second author. We would like to thank one of the anonymous reviewers for very useful suggestions.pl
    dc.description.sponsorshipThis work has been partially supported by the NSERC grant OGP 9207.pl
    dc.language.isoenpl
    dc.publisherUniversity of Białystokpl
    dc.rightsCC BY-SA 4.0-
    dc.rights.urihttps://creativecommons.org/licenses/by-sa/4.0/-
    dc.titleRecognizing Chordal Graphs: Lex BFS and MCSpl
    dc.typeArticlepl
    dc.rights.holder© 2008 Broderick Arneson, Piotr Rudnicki, published by University of Białystokpl
    dc.rights.holderThis work is licensed under the Creative Commons License.pl
    dc.identifier.doi10.2478/v10037-006-0022-z-
    dc.description.AffiliationBroderick Arneson - University of Alberta Edmonton, Canadapl
    dc.description.AffiliationPiotr Rudnicki - University of Alberta Edmonton, Canadapl
    dc.description.referencesBroderick Arneson and Piotr Rudnicki. Chordal graphs. Formalized Mathematics, 14(3):79-92, 2006.pl
    dc.description.referencesGrzegorz Bancerek. Cardinal numbers. Formalized Mathematics, 1(2):377-382, 1990.pl
    dc.description.referencesGrzegorz Bancerek. The fundamental properties of natural numbers. Formalized Mathematics, 1(1):41-46, 1990.pl
    dc.description.referencesGrzegorz Bancerek. The ordinal numbers. Formalized Mathematics, 1(1):91-96, 1990.pl
    dc.description.referencesGrzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Formalized Mathematics, 1(1):107-114, 1990.pl
    dc.description.referencesCzesław Byliński. A classical fi rst order language. Formalized Mathematics, 1(4):669-676, 1990.pl
    dc.description.referencesCzesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1):55-65, 1990.pl
    dc.description.referencesCzesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153-164, 1990.pl
    dc.description.referencesCzesław Byliński. The modi cation of a function by a function and the iteration of the composition of a function. Formalized Mathematics, 1(3):521-527, 1990.pl
    dc.description.referencesCzesław Byliński. Partial functions. Formalized Mathematics, 1(2):357-367, 1990.pl
    dc.description.referencesCzesław Byliński. Some basic properties of sets. Formalized Mathematics, 1(1):47-53, 1990.pl
    dc.description.referencesAgata Darmochwał. Finite sets. Formalized Mathematics, 1(1):165-167, 1990.pl
    dc.description.referencesM. Ch. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.pl
    dc.description.referencesJarosław Kotowicz. Monotone real sequences. Subsequences. Formalized Mathematics, 1(3):471-475, 1990.pl
    dc.description.referencesGilbert Lee. Walks in Graphs. Formalized Mathematics, 13(2):253-269, 2005.pl
    dc.description.referencesGilbert Lee. Weighted and Labeled Graphs. Formalized Mathematics, 13(2):279-293, 2005.pl
    dc.description.referencesGilbert Lee and Piotr Rudnicki. On ordering of bags. Formalized Mathematics, 10(1):39-46, 2002.pl
    dc.description.referencesGilbert Lee and Piotr Rudnicki. Alternative graph structures. Formalized Mathematics, 13(2):235-252, 2005.pl
    dc.description.referencesYatsuka Nakamura, Piotr Rudnicki, Andrzej Trybulec, and Pauline N. Kawamoto. Preliminaries to circuits, I. Formalized Mathematics, 5(2):167-172, 1996.pl
    dc.description.referencesTakaya Nishiyama and Yasuho Mizuhara. Binary arithmetics. Formalized Mathematics, 4(1):83-86, 1993.pl
    dc.description.referencesPiotr Rudnicki. Little Bezout theorem (factor theorem). Formalized Mathematics, 12(1):49-58, 2004.pl
    dc.description.referencesPiotr Rudnicki and Andrzej Trybulec. Abian's fixed point theorem. Formalized Mathematics, 6(3):335-338, 1997.pl
    dc.description.referencesPiotr Rudnicki and Andrzej Trybulec. Multivariate polynomials with arbitrary number of variables. Formalized Mathematics, 9(1):95-110, 2001.pl
    dc.description.referencesChristoph Schwarzweller. Term orders. Formalized Mathematics, 11(1):105-111, 2003.pl
    dc.description.referencesR. E. Tarjan and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput., 13(3):566-579, 1984.pl
    dc.description.referencesAndrzej Trybulec. Subsets of complex numbers. To appear in Formalized Mathematics.pl
    dc.description.referencesAndrzej Trybulec. Domains and their Cartesian products. Formalized Mathematics, 1(1):115-122, 1990.pl
    dc.description.referencesAndrzej Trybulec. Tarski Grothendieck set theory. Formalized Mathematics, 1(1):9-11, 1990.pl
    dc.description.referencesAndrzej Trybulec. Many-sorted sets. Formalized Mathematics, 4(1):15-22, 1993.pl
    dc.description.referencesAndrzej Trybulec. On the sets inhabited by numbers. Formalized Mathematics, 11(4):341-347, 2003.pl
    dc.description.referencesWojciech A. Trybulec. Pigeon hole principle. Formalized Mathematics, 1(3):575-579, 1990.pl
    dc.description.referencesZinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990.pl
    dc.description.referencesEdmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1(1):73-83, 1990.pl
    dc.description.referencesEdmund Woronowicz. Relations defi ned on sets. Formalized Mathematics, 1(1):181-186, 1990.pl
    dc.description.referencesEdmund Woronowicz and Anna Zalewska. Properties of binary relations. Formalized Mathematics, 1(1):85-89, 1990.pl
    dc.identifier.eissn1898-9934-
    dc.description.volume14pl
    dc.description.issue4pl
    dc.description.firstpage187pl
    dc.description.lastpage206pl
    dc.identifier.citation2Formalized Mathematicspl
    Występuje w kolekcji(ach):Formalized Mathematics, 2006, Volume 14, Issue 4

    Pliki w tej pozycji:
    Plik Opis RozmiarFormat 
    Recognizing_Chordal_Graphs_Lex_BFS_and_MCS.pdf160,13 kBAdobe PDFOtwórz
    Pokaż uproszczony widok rekordu Zobacz statystyki


    Pozycja ta dostępna jest na podstawie licencji Licencja Creative Commons CCL Creative Commons