Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
From MaRDI portal
Publication:3007632
DOI10.1007/978-3-642-20712-9_20zbMath1332.68073OpenAlexW1795713683MaRDI QIDQ3007632
Daniël Paulusma, Petr A. Golovach, Jian Song
Publication date: 17 June 2011
Published in: Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/10694/1/10694.pdf
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (3)
The complexity of surjective homomorphism problems-a survey ⋮ Finding vertex-surjective graph homomorphisms ⋮ Graph partitions with prescribed patterns
Cites Work
- Unnamed Item
- Unnamed Item
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- The external constraint 4 nonempty part sandwich problem
- A complete complexity classification of the role assignment problem
- Strong computational lower bounds via parameterized complexity
- Covering graphs with few complete bipartite subgraphs
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- Which problems have strongly exponential complexity?
- \(2K_2\)-partition of some classes of graphs
- A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
- Domination Problems in Nowhere-Dense Classes
- Retractions to Pseudoforests
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Compaction, Retraction, and Constraint Satisfaction
- FindingH-partitions efficiently
- Computational Complexity of Compaction to Reflexive Cycles
- Bi‐arc graphs and the complexity of list homomorphisms
This page was built for publication: Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
