Computational complexity of covering three-vertex multigraphs

DOI10.1016/J.TCS.2015.09.013MaRDI QIDQ897866zbMATH OpenOpenAlexFDO

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

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Computational complexity of covering three-vertex multigraphs
• scientific article; zbMATH DE number 1107736
• Covering regular graphs
• scientific article; zbMATH DE number 91031
• scientific article; zbMATH DE number 1236360

Cites work

• scientific article; zbMATH DE number 4106877 (Why is no real title available?)
• scientific article; zbMATH DE number 91031 (Why is no real title available?)
• scientific article; zbMATH DE number 1236360 (Why is no real title available?)
• scientific article; zbMATH DE number 1107736 (Why is no real title available?)
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Algorithmic aspects of regular graph covers with applications to planar graphs
• An Efficient Algorithm for Graph Isomorphism
• Complexity of hypergraph coloring and Seidel's switching.
• Coverings and minors: Application to local computations in graphs
• K4,4 ?e has no finite planar cover
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• On possible counterexamples to Negami's planar cover conjecture
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The NP-Completeness of Edge-Coloring
• The complexity of satisfiability problems

Cited in

(10)

• scientific article; zbMATH DE number 7724194 (Why is no real title available?)
• An algorithmic framework for locally constrained homomorphisms
• scientific article; zbMATH DE number 6390842 (Why is no real title available?)
• List covering of regular multigraphs
• An algorithmic framework for locally constrained homomorphisms
• Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract)
• Computational complexity of covering disconnected multigraphs
• Computational complexity of covering three-vertex multigraphs
• List covering of regular multigraphs with semi-edges
• scientific article; zbMATH DE number 91031 (Why is no real title available?)

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

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