Product graph representations

DOI10.1002/JGT.3190160508MaRDI QIDQ4020705zbMATHOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(35)

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

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)