Einzeltreffer — DigiBib

International audience ; We present a library for graph theory in Coq/Ssreflect. This library covers various notions on simple graphs, directed graphs, and multigraphs. We use it to formalise several results from the literature: Menger's theorem, the excluded-minor characterization of treewidth-two graphs, and a correspondence between multigraphs of treewidth at most two and terms of certain algebras.

Titel:	Graph Theory in Coq: Minors, Treewidth, and Isomorphisms
Autor/in / Beteiligte Person:	Doczkal, Christian ; Pous, Damien ; Preuves et Langages (PLUME) ; Laboratoire de l'Informatique du Parallélisme (LIP) ; École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL) ; Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL) ; Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS) ; Plume ; ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010) ; European Project: 678157,H2020,ERC-2015-STG,CoVeCe(2016)
Link:	https://hal.science/hal-02316859 https://hal.science/hal-02316859v2/document Volltext https://doi.org/10.1007/s10817-020-09543-2
Zeitschrift:	ISSN: 0168-7433, 2020
Veröffentlichung:	HAL CCSD ; Springer Verlag, 2020
Medientyp:	academicJournal
DOI:	10.1007/s10817-020-09543-2
Schlagwort:	graph theory minor treewidth isomorphisms Coq Ssreflect [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
Sonstiges:	Nachgewiesen in: BASE Sprachen: English Collection: Université de Lyon: HAL Document Type: article in journal/newspaper Language: English Relation: info:eu-repo/grantAgreement//678157/EU/Coinduction for Verification and Certification/CoVeCe; hal-02316859; https://hal.science/hal-02316859; https://hal.science/hal-02316859v2/document; https://hal.science/hal-02316859v2/file/graphscoq.pdf Rights: info:eu-repo/semantics/OpenAccess

Klicken Sie ein Format an und speichern Sie dann die Daten oder geben Sie eine Empfänger-Adresse ein und lassen Sie sich per Email zusenden.

BibTeX Citavi, JabRef, u.a.
(Literaturverwaltung)

PDF kein Volltext!
(Merkzettel, Notizen)

RIS Endnote, Citavi u.a.
(Literaturverwaltung)

MODS
(XML zur Weiterverarbeitung)

oder

Wählen Sie das für Sie passende Zitationsformat und kopieren Sie es dann in die Zwischenablage, lassen es sich per Mail zusenden oder speichern es als PDF-Datei.

Gewünschter Zitations-Stil:

oder

Bitte prüfen Sie, ob die Zitation formal korrekt ist, bevor Sie sie in einer Arbeit verwenden. Benutzen Sie gegebenenfalls den "Exportieren"-Dialog, wenn Sie ein Literaturverwaltungsprogramm verwenden und die Zitat-Angaben selbst formatieren wollen.

Graph Theory in Coq: Minors, Treewidth, and Isomorphisms