A note on Winkler's algorithm for factoring a connected graph

DOI10.1016/0012-365X(92)90283-LMaRDI QIDQ686292zbMATHFDO

Authors Bernhard Hochstrasser

Publication date 14 October 1993

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

connected graphCartesian productprime factorizationWinkler's algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Factoring a graph in polynomial time
• Factoring cardinal product graphs in polynomial time
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Recognizing Cartesian products in linear time
• Unique prime Cartesian factorization of graphs over finite fields

Cites work

• scientific article; zbMATH DE number 4012654 (Why is no real title available?)
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Computing equivalence classes among the edges of a graph with applications
• Distance-preserving subgraphs of hypercubes
• Factoring a graph in polynomial time
• Graph multiplication
• On Isometric Embeddings of Graphs
• Product graph representations

Cited in

(6)

• Vertex Exponential Algorithms for Connected f-Factors
• Computing equivalence classes among the edges of a graph with applications
• Factoring cartesian‐product graphs
• Cartesian graph factorization at logarithmic cost per edge
• Robust Factorizations and Colorings of Tensor Graphs
• Finding the prime factors of strong direct product graphs in polynomial time

This page was built for publication: A note on Winkler's algorithm for factoring a connected graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686292)