Comparing universal covers in polynomial time

DOI10.1007/S00224-009-9200-ZzbMATH Open1205.68260OpenAlexW2087073372MaRDI QIDQ987372FDOQ987372

Daniël Paulusma, Jiří Fiala

Publication date: 13 August 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/7420/1/7420.pdf

Recommendations

• Comparing Universal Covers in Polynomial Time
• Cantor--Bernstein type theorem for locally constrained graph homomorphisms
• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths
• scientific article; zbMATH DE number 2081019
• Locally constrained graph homomorphisms and equitable partitions

zbMATH Keywords

computational complexitygraph homomorphismuniversal coverdegree matrix

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Computing Boolean functions on anonymous networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Role colouring a graph
• How hard is it to determine if a graph has a 2-role assignment?
• Title not available (Why is that?)
• Title not available (Why is that?)
• The role assignment model nearly fits most social networks
• A complete complexity classification of the role assignment problem
• Homomorphisms of derivative graphs
• Title not available (Why is that?)
• Fixed-parameter complexity of \(\lambda\)-labelings
• Locally constrained graph homomorphisms and equitable partitions
• Title not available (Why is that?)
• Automata, Languages and Programming
• Covering regular graphs
• Partial covers of graphs
• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths
• Title not available (Why is that?)
• Finite common coverings of pairs of regular graphs
• Title not available (Why is that?)
• Cantor--Bernstein type theorem for locally constrained graph homomorphisms
• Constructing 5-Arc-Transitive Cubic Graphs
• Faster Subtree Isomorphism
• Comparing Universal Covers in Polynomial Time
• Title not available (Why is that?)

Cited In (10)

• Comparing Universal Covers in Polynomial Time
• An algorithmic framework for locally constrained homomorphisms
• Computing role assignments of split graphs
• Computing role assignments of proper interval graphs in polynomial time
• Computing role assignments of chordal graphs
• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths
• Title not available (Why is that?)
• An algorithmic framework for locally constrained homomorphisms
• Computing Role Assignments of Proper Interval Graphs in Polynomial Time
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

This page was built for publication: Comparing universal covers in polynomial time

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