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_42zbMATH Open1382.05071OpenAlexW6148599MaRDI QIDQ4925263FDOQ4925263
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
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
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph operations (line graphs, products, etc.) (05C76)
Cited In (5)
- Boundary vertices of Cartesian product of directed graphs
- Decompositions of graphs based on a new graph product
- Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
- Fast factorization of Cartesian products of (directed) hypergraphs
- Note on decompositions based on the vertex-removing synchronised graph product
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)
