About: On the Complexity of Paths Avoiding Forbidden Pairs     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
  • Given a graph $G=(V,E)$, two fixed vertices $s,t\in V$ and a set $F$ of pairs of vertices (called {\em forbidden pairs}), the {\em problem of a path avoiding forbidden pairs} is to find a path from $s$ to $t$ that contains at most one vertex from each pair in $F$. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in P. We study the complexity of the problem for directed acyclic graphs with respect to the structure of the forbidden pairs.
  • Given a graph $G=(V,E)$, two fixed vertices $s,t\in V$ and a set $F$ of pairs of vertices (called {\em forbidden pairs}), the {\em problem of a path avoiding forbidden pairs} is to find a path from $s$ to $t$ that contains at most one vertex from each pair in $F$. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in P. We study the complexity of the problem for directed acyclic graphs with respect to the structure of the forbidden pairs. (en)
Title
  • On the Complexity of Paths Avoiding Forbidden Pairs
  • On the Complexity of Paths Avoiding Forbidden Pairs (en)
skos:prefLabel
  • On the Complexity of Paths Avoiding Forbidden Pairs
  • On the Complexity of Paths Avoiding Forbidden Pairs (en)
skos:notation
  • RIV/00216208:11320/09:00207043!RIV10-GA0-11320___
http://linked.open...avai/riv/aktivita
http://linked.open...avai/riv/aktivity
  • P(1M0545), P(GA201/09/0197), Z(MSM0021620838)
http://linked.open...iv/cisloPeriodika
  • 13
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
  • 331496
http://linked.open...ai/riv/idVysledku
  • RIV/00216208:11320/09:00207043
http://linked.open...riv/jazykVysledku
http://linked.open.../riv/klicovaSlova
  • Complexity; Paths; Avoiding; Forbidden; Pairs (en)
http://linked.open.../riv/klicoveSlovo
http://linked.open...odStatuVydavatele
  • NL - Nizozemsko
http://linked.open...ontrolniKodProRIV
  • [03D367C8EF66]
http://linked.open...i/riv/nazevZdroje
  • Discrete Applied Mathematics
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
  • 157
http://linked.open...iv/tvurceVysledku
  • Kolman, Petr
  • Pangrác, Ondřej
http://linked.open...ain/vavai/riv/wos
  • 000267586700011
http://linked.open...n/vavai/riv/zamer
issn
  • 0166-218X
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, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software