Finding vertex-surjective graph homomorphisms (Q715053)

From MaRDI portal

Jump to:navigation, search

scientific article

In more languages

Language	Label	Description	Also known as
English	Finding vertex-surjective graph homomorphisms	scientific article

Statements

scholarly article

Finding vertex-surjective graph homomorphisms (English)

zbMATH Open document ID

10.1007/s00236-012-0164-0

Petr A. Golovach

Bernard Lidický

Daniël Paulusma

Acta Informatica

publication date

15 October 2012

full work available at URL

http://dro.dur.ac.uk/10697/1/10697.pdf

Mathematics Subject Classification ID

zbMATH DE Number

zbMATH Keywords

surjective homomorphism problem

guest graph

host graph

NP-complete

MaRDI profile type

MaRDI publication profile

Parameterized Algorithms for Boxicity

The complexity of surjective homomorphism problems-a survey

Improved Parameterized Upper Bounds for Vertex Cover

Upper bounds to the clique width of graphs

What Makes Equitable Connected Partition Easy

Retractions to Pseudoforests

Graph Layout Problems Parameterized by Vertex Cover

Locally constrained graph homomorphisms -- structure, complexity, and applications

Parameterized complexity of coloring problems: treewidth versus vertex cover

A complete complexity classification of the role assignment problem

An application of simultaneous diophantine approximation in combinatorial optimization

Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees

The complexity of homomorphism and constraint satisfaction problems seen from the other side

On the complexity of H-coloring

Integer Programming with a Fixed Number of Variables

Computational Complexity of Compaction to Reflexive Cycles

Compaction, Retraction, and Constraint Satisfaction

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

Sitelinks

Mathematics(1 entry)

mardi Publication:715053

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q715053&oldid=35302616"