elib
DLR-Header
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

Abstract

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
Authors:
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Backhouse, RolandUniversity of Nottinghamhttps://orcid.org/0000-0002-0140-8089
Doornbos, HenkUNSPECIFIEDUNSPECIFIED
Glück, RolandUNSPECIFIEDhttps://orcid.org/0000-0001-7909-1942
van der Woude, JaapEindhoven University of TechnologyUNSPECIFIED
Date:2021
Journal or Publication Title:Journal of Logical and Algebraic Methods in Programming
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In SCOPUS:Yes
In ISI Web of Science:Yes
Volume:124
DOI:10.1016/j.jlamp.2021.100730
Page Range:pp. 1-47
Editors:
EditorsEmailEditor's ORCID iD
De Nicola, RoccoIMT School for Advanced Studieshttps://orcid.org/0000-0003-4691-7570
Publisher:Elsevier
ISSN:2352-2208
Status:Published
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:09 Nov 2021 13:48

Repository Staff Only: item control page

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