DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

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

Backhouse, Roland and Doornbos, Henk and Glück, Roland and 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, pp. 1-47. Elsevier. doi: 10.1016/j.jlamp.2021.100730. ISSN 2352-2208.

Full text not available from this repository.

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


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.

Item URL in elib:https://elib.dlr.de/145301/
Document Type:Article
Title:Components and acyclicity of graphs. An exercise in combining precision with concision
AuthorsInstitution or Email of AuthorsAuthor's ORCID iDORCID Put Code
Backhouse, RolandUniversity of Nottinghamhttps://orcid.org/0000-0002-0140-8089UNSPECIFIED
Glück, RolandUNSPECIFIEDhttps://orcid.org/0000-0001-7909-1942UNSPECIFIED
van der Woude, JaapEindhoven University of TechnologyUNSPECIFIEDUNSPECIFIED
Date:15 October 2021
Journal or Publication Title:Journal of Logical and Algebraic Methods in Programming
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In ISI Web of Science:Yes
Page Range:pp. 1-47
EditorsEmailEditor's ORCID iDORCID Put Code
De Nicola, RoccoIMT School for Advanced Studieshttps://orcid.org/0000-0003-4691-7570UNSPECIFIED
Keywords:Relation Algebra, Grapg Theory, Connected Components, Cyclicity
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space System Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Space System Technology
DLR - Research theme (Project):R - Project Factory of the Future
Location: Augsburg
Institutes and Institutions:Institute of Structures and Design > Automation and Production Technology
Deposited By: Glück, Dr. Roland
Deposited On:09 Nov 2021 13:48
Last Modified:04 Dec 2023 12:50

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.