A Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph with Regard to the Cartesian Product

DOI10.1007/978-3-642-38768-5_42zbMath1382.05071OpenAlexW6148599MaRDI QIDQ4925263

Éric Thierry, Christophe Crespelle, Thomas Lambert

Publication date: 11 June 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-38768-5_42

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Graph operations (line graphs, products, etc.) (05C76)

Related Items (3)

Fast factorization of Cartesian products of (directed) hypergraphs ⋮ Boundary vertices of Cartesian product of directed graphs ⋮ Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time

This page was built for publication: A Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph with Regard to the Cartesian Product