Product graph representations

DOI10.1002/jgt.3190160508zbMath0766.05092OpenAlexW2109534718MaRDI QIDQ4020705

Tomás Feder

Publication date: 17 January 1993

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190160508

zbMATH Keywords

algorithmscanonical representationsisometric representationcartesian prime factorizationproduct graph representation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Graph theory (05C99)

Related Items (31)

Algorithm for recognizing Cartesian graph bundles ⋮ Convexity in finite metric spaces ⋮ The algebra of metric betweenness. I: Subdirect representation and retraction ⋮ On the natural imprint function of a graph ⋮ Recognizing Cartesian graph bundles ⋮ Recognizing halved cubes in a constant time per edge ⋮ Recognizing Cartesian products in linear time ⋮ On finding convex cuts in general, bipartite and plane graphs ⋮ Partial cubes and their \(\tau\)-graphs ⋮ Factoring cartesian‐product graphs ⋮ Recognizing some complementary products ⋮ Skeletons, recognition algorithm and distance matrix of quasi-median graphs ⋮ Unique square property, equitable partitions, and product-like graphs ⋮ Quasi-median graphs, their generalizations, and tree-like equalities ⋮ Unnamed Item ⋮ Factorization and pseudofactorization of weighted graphs ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Fast factorization of Cartesian products of (directed) hypergraphs ⋮ Isometric Hamming embeddings of weighted graphs ⋮ Structure of Fibonacci cubes: a survey ⋮ Fibonacci \((p,r)\)-cubes as Cartesian products ⋮ On Cartesian products of signed graphs ⋮ Computing equivalence classes among the edges of a graph with applications ⋮ Finding the prime factors of strong direct product graphs in polynomial time ⋮ A note on Winkler's algorithm for factoring a connected graph ⋮ A new fixed point approach for stable networks and stable marriages ⋮ Cartesian graph factorization at logarithmic cost per edge ⋮ Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time ⋮ Recognizing median graphs in subquadratic time ⋮ Factoring cardinal product graphs in polynomial time ⋮ Characterizing flag graphs and incuced subgraphs of Cartesian product graphs

Cites Work

• Factoring a graph in polynomial time
• Absolute Retracts and Varieties of Reflexive Graphs
• On the Addressing Problem for Loop Switching

This page was built for publication: Product graph representations