This HTML5 document contains 49 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n12http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n22http://purl.org/net/nknouf/ns/bibtex#
n5http://localhost/temp/predkladatel/
n10http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n6http://linked.opendata.cz/resource/domain/vavai/projekt/
n20http://linked.opendata.cz/ontology/domain/vavai/
n18http://linked.opendata.cz/resource/domain/vavai/zamer/
n17https://schema.org/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n8http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216208%3A11320%2F08%3A00207284%21RIV10-GA0-11320___/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n11http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n4http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n14http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n9http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n21http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n19http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n13http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216208%3A11320%2F08%3A00207284%21RIV10-GA0-11320___
rdf:type
skos:Concept n20:Vysledek
dcterms:description
We use a connection between polymorphisms and the structure of smooth digraphs to prove the conjecture of Bang-Jensen and Hell from 1990 and, as a consequence, a conjecture of Bang-Jensen, Hell and MacGillivray from 1995. The conjectured characterization of computationally complex coloring problems for smooth digraphs is proved using tools of universal algebra. We cite further graph results obtained using this new approach. The proofs are based in an universal algebraic framework developed for the Constraint Satisfaction Problem and the CSP dichotomy conjecture of Feder and Vardi in particular. We use a connection between polymorphisms and the structure of smooth digraphs to prove the conjecture of Bang-Jensen and Hell from 1990 and, as a consequence, a conjecture of Bang-Jensen, Hell and MacGillivray from 1995. The conjectured characterization of computationally complex coloring problems for smooth digraphs is proved using tools of universal algebra. We cite further graph results obtained using this new approach. The proofs are based in an universal algebraic framework developed for the Constraint Satisfaction Problem and the CSP dichotomy conjecture of Feder and Vardi in particular.
dcterms:title
Graphs, Polymorphisms and the Complexity of Homomorphism Problems Graphs, Polymorphisms and the Complexity of Homomorphism Problems
skos:prefLabel
Graphs, Polymorphisms and the Complexity of Homomorphism Problems Graphs, Polymorphisms and the Complexity of Homomorphism Problems
skos:notation
RIV/00216208:11320/08:00207284!RIV10-GA0-11320___
n3:aktivita
n9:Z n9:P
n3:aktivity
P(GA201/06/0664), P(LC505), Z(MSM0021620839)
n3:dodaniDat
n13:2010
n3:domaciTvurceVysledku
Kozik, Marcin n10:6798268 Niven, Todd
n3:druhVysledku
n19:D
n3:duvernostUdaju
n4:S
n3:entitaPredkladatele
n8:predkladatel
n3:idSjednocenehoVysledku
369610
n3:idVysledku
RIV/00216208:11320/08:00207284
n3:jazykVysledku
n14:eng
n3:klicovaSlova
Graphs; Polymorphisms; Complexity; Homomorphism; Problems
n3:klicoveSlovo
n11:Complexity n11:Polymorphisms n11:Problems n11:Homomorphism n11:Graphs
n3:kontrolniKodProRIV
[C1AB36B1DCB9]
n3:mistoKonaniAkce
Kanada
n3:mistoVydani
Kanada
n3:nazevZdroje
Proccedings of the 40th ACM Symposium on Theory of Computing, STOC´08
n3:obor
n21:BA
n3:pocetDomacichTvurcuVysledku
3
n3:pocetTvurcuVysledku
3
n3:projekt
n6:LC505 n6:GA201%2F06%2F0664
n3:rokUplatneniVysledku
n13:2008
n3:tvurceVysledku
Kozik, Marcin Niven, Todd Barto, Libor
n3:typAkce
n12:WRD
n3:wos
000266622800085
n3:zahajeniAkce
2008-01-01+01:00
n3:zamer
n18:MSM0021620839
s:numberOfPages
8
n22:hasPublisher
ACM Kanada
n17:isbn
978-1-60558-047-0
n5:organizacniJednotka
11320