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_42MaRDI QIDQ4925263zbMATH OpenOpenAlexFDO

Authors Christophe Crespelle, Eric Thierry, 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

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

Recommendations

• Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
• Recognizing Cartesian products in linear time
• On the Cartesian skeleton and the factorization of the strong product of digraphs
• Fast factorization of Cartesian products of (directed) hypergraphs
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs

Cited in

(5)

• Decompositions of graphs based on a new graph product
• 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
• Note on decompositions based on the vertex-removing synchronised graph product
• Fast factorization of Cartesian products of (directed) hypergraphs

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

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