Computational complexity of covering three-vertex multigraphs

DOI10.1016/j.tcs.2015.09.013zbMath1331.68108OpenAlexW1954345120MaRDI QIDQ897866

Jan Kratochvíl, Marek Tesař, Jan Arne Telle

Publication date: 8 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.09.013

zbMATH Keywords

computational complexitygraph homomorphismcovering projection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

List covering of regular multigraphs ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ List covering of regular multigraphs with semi-edges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Coverings and minors: Application to local computations in graphs
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The NP-Completeness of Edge-Coloring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• K4,4 ?e has no finite planar cover
• On possible counterexamples to Negami's planar cover conjecture
• Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs
• The complexity of satisfiability problems
• An Efficient Algorithm for Graph Isomorphism
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Computational complexity of covering three-vertex multigraphs