Computing vertex-surjective homomorphisms to partially reflexive trees
DOI10.1016/J.TCS.2012.06.039zbMATH Open1251.05031OpenAlexW2056827961MaRDI QIDQ714844FDOQ714844
Jian Song, Petr A. Golovach, Daniël Paulusma
Publication date: 11 October 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.06.039
Recommendations
Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Graph theory
- Title not available (Why is that?)
- On the complexity of H-coloring
- Which problems have strongly exponential complexity?
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The complexity of surjective homomorphism problems-a survey
- The complexity of satisfiability problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- A complete complexity classification of the role assignment problem
- Strong computational lower bounds via parameterized complexity
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- Linear time low tree-width partitions and algorithmic consequences
- List homomorphisms to reflexive graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
- Algorithms for Partition of Some Class of Graphs under Compaction
- Compaction, Retraction, and Constraint Satisfaction
- FindingH-partitions efficiently
- Computational Complexity of Compaction to Reflexive Cycles
- Covering graphs with few complete bipartite subgraphs
- Finding Vertex-Surjective Graph Homomorphisms
- Retractions to Pseudoforests
- \(2K_2\)-partition of some classes of graphs
- Title not available (Why is that?)
Cited In (10)
- The Complexity of Counting Surjective Homomorphisms and Compactions
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- Algebraic global gadgetry for surjective constraint satisfaction
- Surjective \(H\)-colouring: new hardness results
- Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
- Title not available (Why is that?)
- An algebraic hardness criterion for surjective constraint satisfaction.
- Complexity of correspondence \(H\)-colourings
- On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
- Finding matching cuts in \(H\)-free graphs
This page was built for publication: Computing vertex-surjective homomorphisms to partially reflexive trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714844)
