Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time

DOI10.1016/j.disc.2015.06.001zbMath1317.05163OpenAlexW1036516582MaRDI QIDQ2515582

Christophe Crespelle, Éric Thierry

Publication date: 5 August 2015

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

Full work available at URL: https://doi.org/10.1016/j.disc.2015.06.001

zbMATH Keywords

Cartesian productdirected graphsgraph decompositionslinear-time algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Cartesian products of directed graphs with loops, Digraphs Products

Cites Work

• Unnamed Item
• Unnamed Item
• Factoring a graph in polynomial time
• Graph multiplication
• The strong perfect graph theorem
• Recognizing Cartesian products in linear time
• Ordering the order of a distributive lattice by itself
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Strict refinement for graphs and digraphs
• Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
• Cartesian graph factorization at logarithmic cost per edge
• Efficient graph representations
• Product graph representations
• A Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph with Regard to the Cartesian Product