Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
From MaRDI portal
Publication:2515582
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
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
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