Comparing universal covers in polynomial time

DOI10.1007/s00224-009-9200-zzbMath1205.68260OpenAlexW2087073372MaRDI QIDQ987372

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

zbMATH Keywords

computational complexitygraph homomorphismuniversal coverdegree matrix

Mathematics Subject Classification ID

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

Related Items

Computing role assignments of split graphs ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Computing role assignments of proper interval graphs in polynomial time ⋮ Computing Role Assignments of Proper Interval Graphs in Polynomial Time ⋮ Computing role assignments of chordal graphs ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

Cites Work

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