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

DOI10.1016/J.JLAMP.2021.100730MaRDI QIDQ2667191zbMATH OpenOpenAlexFDO

Authors Henk Doornbos, Roland Glück, Jaap van der Woude, Roland C. Backhouse

Publication date 24 November 2021

Published in Journal of Logical and Algebraic Methods in Programming (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/j.jlamp.2021.100730

zbMATH Keywords

acyclic graphcalculational methodpoint-free reasoningregular algebrarelation algebrastrongly connected component

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A simplified correctness proof for a well-known algorithm computing strongly connected components.
• Algebraic investigation of connected components
• Enumeration of connected components of acyclic digraph
• Graphs and graph algorithms
• scientific article; zbMATH DE number 914491

Cites work

• A calculational approach to mathematical induction
• A comparison of gaussian and gauss-jordan elimination in regular algebra
• Algebraic investigation of connected components
• An analysis of repeated graph search
• Calculating path algorithms
• Demonic operators and monotype factors
• Efficient string matching
• Factor theory and the unity of opposites
• Fast Pattern Matching in Strings
• Fixed-point calculus
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 45228 (Why is no real title available?)
• scientific article; zbMATH DE number 3550201 (Why is no real title available?)
• scientific article; zbMATH DE number 977284 (Why is no real title available?)
• scientific article; zbMATH DE number 2087342 (Why is no real title available?)
• scientific article; zbMATH DE number 890353 (Why is no real title available?)
• scientific article; zbMATH DE number 1434122 (Why is no real title available?)
• scientific article; zbMATH DE number 3366846 (Why is no real title available?)
• Programming from metaphorisms
• Regular algebra applied to language problems
• Regular Algebra Applied to Path-finding Problems
• Relations binaires, fermetures, correspondances de Galois
• Roots of Star Events
• The loop complexity of pure-group events

Cited in

(4)

• Algebraic investigation of connected components
• On difunctions
• The index and core of a relation. With applications to the axiomatics of relation algebra
• An example of goal-directed, calculational proof

This page was built for publication: Components and acyclicity of graphs. An exercise in combining precision with concision

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2667191)