About: The CSP dichotomy holds for digraphs with no sources and no sinks ( A positive answer to a conjecture of Bang-Jensen and Hell)     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

AttributesValues
rdf:type
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. (en)
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) (en)
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) (en)
skos:notation
  • RIV/00216208:11320/09:00207006!RIV10-GA0-11320___
http://linked.open...avai/riv/aktivita
http://linked.open...avai/riv/aktivity
  • P(GA201/06/0664), P(LC505), Z(MSM0021620839)
http://linked.open...iv/cisloPeriodika
  • 5
http://linked.open...vai/riv/dodaniDat
http://linked.open...aciTvurceVysledku
http://linked.open.../riv/druhVysledku
http://linked.open...iv/duvernostUdaju
http://linked.open...titaPredkladatele
http://linked.open...dnocenehoVysledku
  • 308646
http://linked.open...ai/riv/idVysledku
  • RIV/00216208:11320/09:00207006
http://linked.open...riv/jazykVysledku
http://linked.open.../riv/klicovaSlova
  • dichotomy; holds; digraphs; sources; sinks; positive; answer; conjecture; Bang-Jensen (en)
http://linked.open.../riv/klicoveSlovo
http://linked.open...odStatuVydavatele
  • US - Spojené státy americké
http://linked.open...ontrolniKodProRIV
  • [271C8EF76B54]
http://linked.open...i/riv/nazevZdroje
  • SIAM Journal on Computing
http://linked.open...in/vavai/riv/obor
http://linked.open...ichTvurcuVysledku
http://linked.open...cetTvurcuVysledku
http://linked.open...vavai/riv/projekt
http://linked.open...UplatneniVysledku
http://linked.open...v/svazekPeriodika
  • 38
http://linked.open...iv/tvurceVysledku
  • Barto, Libor
  • Kozik, Marcin
  • Niven, Todd
http://linked.open...ain/vavai/riv/wos
  • 000264353000006
http://linked.open...n/vavai/riv/zamer
issn
  • 0097-5397
number of pages
http://localhost/t...ganizacniJednotka
  • 11320
Faceted Search & Find service v1.16.118 as of Jun 21 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 77 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software