Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time

DOI10.1016/0166-218X(86)90023-5zbMath0637.05018WikidataQ114215020 ScholiaQ114215020MaRDI QIDQ1098860

Joan Feigenbaum

Publication date: 1986

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

digraphsCartesian productdirected graphsprime factorizations

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (11)

Fast factorization of Cartesian products of (directed) hypergraphs ⋮ Cartesian products of directed graphs with loops ⋮ On the Cartesian skeleton and the factorization of the strong product of digraphs ⋮ Boundary vertices of Cartesian product of directed graphs ⋮ Finding the prime factors of strong direct product graphs in polynomial time ⋮ Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs ⋮ Cartesian graph factorization at logarithmic cost per edge ⋮ Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time ⋮ Direct product of automorphism groups of digraphs ⋮ Digraphs Products ⋮ Strict refinement for graphs and digraphs

Cites Work

• Factoring a graph in polynomial time
• Graph multiplication
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Strict refinement for graphs and digraphs

This page was built for publication: Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time