Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time (Q1098860)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time |
scientific article |
Statements
Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time (English)
0 references
1986
0 references
This note shows that directed graphs have unique prime factorizations under Cartesian multiplication, and the prime factorizations of weakly connected digraphs can be found in polynomial time.
0 references
digraphs
0 references
Cartesian product
0 references
directed graphs
0 references
prime factorizations
0 references
