Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
type: Item
instance of: scholarly article
title: Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
zbMATH Open document ID: 0637.05018
DOI: 10.1016/0166-218X(86)90023-5
author: Joan Feigenbaum
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4037887
zbMATH Keywords: digraphs
zbMATH Keywords: Cartesian product
zbMATH Keywords: directed graphs
zbMATH Keywords: prime factorizations
Wikidata QID: Q114215020
MaRDI profile type: Publication
cites work: A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
cites work: Graph multiplication
cites work: Strict refinement for graphs and digraphs
cites work: Factoring a graph in polynomial time
description: scientific article; zbMATH DE number 4037887