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

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

Namespace Prefixes

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

Statements

Subject Item
n2:RIV%2F00216208%3A11320%2F09%3A00207006%21RIV10-GA0-11320___
rdf:type
n3:Vysledek skos:Concept
dcterms:description
Bang-Jensen and Hell conjectured in 1990 (using the language of graph homomorphisms) a constraint satisfaction problem (CSP) dichotomy for digraphs with no sources or sinks. The conjecture states that the CSP for such a digraph is tractable if each component of its core is a cycle and is NP-complete otherwise. In this paper we prove this conjecture and, as a consequence, a conjecture of Bang-Jensen, Hell, and MacGillivray from 1995 classifying hereditarily hard digraphs. Further, we show that the CSP dichotomy for digraphs with no sources or sinks agrees with the algebraic characterization conjectured by Bulatov, Jeavons, and Krokhin in 2005. Bang-Jensen and Hell conjectured in 1990 (using the language of graph homomorphisms) a constraint satisfaction problem (CSP) dichotomy for digraphs with no sources or sinks. The conjecture states that the CSP for such a digraph is tractable if each component of its core is a cycle and is NP-complete otherwise. In this paper we prove this conjecture and, as a consequence, a conjecture of Bang-Jensen, Hell, and MacGillivray from 1995 classifying hereditarily hard digraphs. Further, we show that the CSP dichotomy for digraphs with no sources or sinks agrees with the algebraic characterization conjectured by Bulatov, Jeavons, and Krokhin in 2005.
dcterms:title
The CSP dichotomy holds for digraphs with no sources and no sinks ( A positive answer to a conjecture of Bang-Jensen and Hell) The CSP dichotomy holds for digraphs with no sources and no sinks ( A positive answer to a conjecture of Bang-Jensen and Hell)
skos:prefLabel
The CSP dichotomy holds for digraphs with no sources and no sinks ( A positive answer to a conjecture of Bang-Jensen and Hell) The CSP dichotomy holds for digraphs with no sources and no sinks ( A positive answer to a conjecture of Bang-Jensen and Hell)
skos:notation
RIV/00216208:11320/09:00207006!RIV10-GA0-11320___
n4:aktivita
n14:P n14:Z
n4:aktivity
P(GA201/06/0664), P(LC505), Z(MSM0021620839)
n4:cisloPeriodika
5
n4:dodaniDat
n11:2010
n4:domaciTvurceVysledku
n8:6798268 Kozik, Marcin
n4:druhVysledku
n12:J
n4:duvernostUdaju
n18:S
n4:entitaPredkladatele
n17:predkladatel
n4:idSjednocenehoVysledku
308646
n4:idVysledku
RIV/00216208:11320/09:00207006
n4:jazykVysledku
n9:eng
n4:klicovaSlova
dichotomy; holds; digraphs; sources; sinks; positive; answer; conjecture; Bang-Jensen
n4:klicoveSlovo
n13:digraphs n13:positive n13:sources n13:conjecture n13:dichotomy n13:sinks n13:Bang-Jensen n13:holds n13:answer
n4:kodStatuVydavatele
US - Spojené státy americké
n4:kontrolniKodProRIV
[271C8EF76B54]
n4:nazevZdroje
SIAM Journal on Computing
n4:obor
n16:BA
n4:pocetDomacichTvurcuVysledku
2
n4:pocetTvurcuVysledku
3
n4:projekt
n10:LC505 n10:GA201%2F06%2F0664
n4:rokUplatneniVysledku
n11:2009
n4:svazekPeriodika
38
n4:tvurceVysledku
Barto, Libor Niven, Todd Kozik, Marcin
n4:wos
000264353000006
n4:zamer
n5:MSM0021620839
s:issn
0097-5397
s:numberOfPages
21
n19:organizacniJednotka
11320