Product graph representations

DOI10.1002/JGT.3190160508zbMATH Open0766.05092OpenAlexW2109534718MaRDI QIDQ4020705FDOQ4020705

Authors: 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

Recommendations

• Recognizing Cartesian products in linear time
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Canonical representations of partial 2- and 3-trees
• Fast recognition of direct and strong products
• Cartesian products of directed graphs with loops

zbMATH Keywords

algorithmsisometric representationcanonical representationscartesian 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)

Cites Work

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

Cited In (36)

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

This page was built for publication: Product graph representations

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