Comparing universal covers in polynomial time

DOI10.1007/s00224-009-9200-zzbMath1205.68260MaRDI 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 complexity; graph homomorphism; universal cover; degree matrix

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

90C59: Approximation methods and heuristics in mathematical programming

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Computing role assignments of split graphs, 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, Computing Role Assignments of Proper Interval Graphs in Polynomial Time

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
• 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
• Unnamed Item