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

DOI10.1016/0012-365X(92)90283-LzbMATH Open0780.05045MaRDI QIDQ686292FDOQ686292

Authors: Bernhard Hochstrasser 

Publication date: 14 October 1993

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

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

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)

Cites Work

• Graph multiplication
• Distance-preserving subgraphs of hypercubes
• On Isometric Embeddings of Graphs
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Product graph representations
• Factoring a graph in polynomial time
• Title not available (Why is that?)
• Computing equivalence classes among the edges of a graph with applications

Cited In (6)

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

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)