Computational complexity of covering three-vertex multigraphs
DOI10.1016/J.TCS.2015.09.013zbMATH Open1331.68108OpenAlexW1954345120MaRDI QIDQ897866FDOQ897866
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
Recommendations
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)
Cites Work
- 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
- The complexity of satisfiability problems
- Coverings and minors: Application to local computations in graphs
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- An Efficient Algorithm for Graph Isomorphism
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- K4,4 ?e has no finite planar cover
- Title not available (Why is that?)
- On possible counterexamples to Negami's planar cover conjecture
- Complexity of hypergraph coloring and Seidel's switching.
- Algorithmic aspects of regular graph covers with applications to planar graphs
Cited In (10)
- Title not available (Why is that?)
- An algorithmic framework for locally constrained homomorphisms
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
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)
