elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

Components and acyclicity of graphs. An exercise in combining precision with concision

Backhouse, Roland und Doornbos, Henk und Glück, Roland und van der Woude, Jaap (2021) Components and acyclicity of graphs. An exercise in combining precision with concision. Journal of Logical and Algebraic Methods in Programming, 124, Seiten 1-47. Elsevier. doi: 10.1016/j.jlamp.2021.100730. ISSN 2352-2208.

Dieses Archiv kann nicht den Volltext zur Verfügung stellen.

Offizielle URL: https://www.sciencedirect.com/science/article/pii/S2352220821000936

Kurzfassung

Central to algorithmic graph theory are the concepts of acyclicity and strongly connected components of a graph, and the related search algorithms. This article is about combining mathematical precision and concision in the presentation of these concepts. Concise formulations are given for, for example, the reflexive-transitive reduction of an acyclic graph, reachability properties of acyclic graphs and their relation to the fundamental concept of “definiteness”, and the decomposition of paths in a graph via the identification of its strongly connected components and a pathwise homomorphic acyclic subgraph. The relevant properties are established by precise algebraic calculation. The combination of concision and precision is achieved by the use of point-free relation algebra capturing the algebraic properties of paths in graphs, as opposed to the use of pointwise reasoning about paths between nodes in graphs.

elib-URL des Eintrags:https://elib.dlr.de/145301/
Dokumentart:Zeitschriftenbeitrag
Titel:Components and acyclicity of graphs. An exercise in combining precision with concision
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Backhouse, RolandUniversity of Nottinghamhttps://orcid.org/0000-0002-0140-8089NICHT SPEZIFIZIERT
Doornbos, HenkNICHT SPEZIFIZIERTNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Glück, RolandRoland.Glueck (at) dlr.dehttps://orcid.org/0000-0001-7909-1942NICHT SPEZIFIZIERT
van der Woude, JaapEindhoven University of TechnologyNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datum:15 Oktober 2021
Erschienen in:Journal of Logical and Algebraic Methods in Programming
Referierte Publikation:Ja
Open Access:Ja
Gold Open Access:Nein
In SCOPUS:Ja
In ISI Web of Science:Ja
Band:124
DOI:10.1016/j.jlamp.2021.100730
Seitenbereich:Seiten 1-47
Herausgeber:
HerausgeberInstitution und/oder E-Mail-Adresse der HerausgeberHerausgeber-ORCID-iDORCID Put Code
De Nicola, RoccoIMT School for Advanced Studieshttps://orcid.org/0000-0003-4691-7570NICHT SPEZIFIZIERT
Verlag:Elsevier
ISSN:2352-2208
Status:veröffentlicht
Stichwörter:Relation Algebra, Grapg Theory, Connected Components, Cyclicity
HGF - Forschungsbereich:Luftfahrt, Raumfahrt und Verkehr
HGF - Programm:Raumfahrt
HGF - Programmthema:Technik für Raumfahrtsysteme
DLR - Schwerpunkt:Raumfahrt
DLR - Forschungsgebiet:R SY - Technik für Raumfahrtsysteme
DLR - Teilgebiet (Projekt, Vorhaben):R - Projekt Factory of the Future
Standort: Augsburg
Institute & Einrichtungen:Institut für Bauweisen und Strukturtechnologie > Automation und Produktionstechnologie
Hinterlegt von: Glück, Dr. Roland
Hinterlegt am:09 Nov 2021 13:48
Letzte Änderung:04 Dez 2023 12:50

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.