In computer science, st-connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s. Formally, the decision problem is given by PATH = {⟨D, s, t⟩ | D is a directed graph with a path from vertex s to t}.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Connectivitat-st (ca)
- Erreichbarkeitsproblem in Graphen (de)
- St-connectivity (it)
- St-connectivity (en)
- Conectividade st (pt)
|
| rdfs:comment
| - En teoria de la complexitat, el problema de connectivitat-st o STCON (pel nom en anglès st-connectivity) és un problema de decisió tal que donat un graf dirigit, cal saber si un vèrtex t és accessible des de s. Formalment, el problema es descriu així: CAMÍ = | D és un graf dirigit amb un camí del vèrtex s cap al vèrtex t (ca)
- In computer science, st-connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s. Formally, the decision problem is given by PATH = {⟨D, s, t⟩ | D is a directed graph with a path from vertex s to t}. (en)
- In informatica, la st-connectivity (o STCON) è il problema decisionale che consiste nel verificare se, dati due vertici e di un grafo orientato, è raggiungibile da . (it)
- Em ciência da computação e teoria da complexidade computacional, conectividade st é um problema de decisão onde dados os vértices s e t de um grafo direcionado, questiona-se se t é acessível partindo de s. Formalmente, o problema de decisão é dada por PATH = {⟨D, s, t⟩ | D é um grafo direcionado com um caminho do vértice s para outro vértice t}. (pt)
- Das Erreichbarkeitsproblem in Graphen (auch STCON bzw. USTCON, GAP, PATH oder REACH) behandelt die Frage, ob es in einem Graphen einen Weg von einem Knoten zu einem Knoten gibt. Existiert solch ein Weg, so ist von aus erreichbar. Andernfalls ist von aus nicht erreichbar. GAP steht für engl. Graph Accessibility Problem und REACH für engl. Reachability. Es lässt sich beispielsweise mit Hilfe der Breitensuche oder der Tiefensuche lösen. (de)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - En teoria de la complexitat, el problema de connectivitat-st o STCON (pel nom en anglès st-connectivity) és un problema de decisió tal que donat un graf dirigit, cal saber si un vèrtex t és accessible des de s. Formalment, el problema es descriu així: CAMÍ = | D és un graf dirigit amb un camí del vèrtex s cap al vèrtex t (ca)
- Das Erreichbarkeitsproblem in Graphen (auch STCON bzw. USTCON, GAP, PATH oder REACH) behandelt die Frage, ob es in einem Graphen einen Weg von einem Knoten zu einem Knoten gibt. Existiert solch ein Weg, so ist von aus erreichbar. Andernfalls ist von aus nicht erreichbar. GAP steht für engl. Graph Accessibility Problem und REACH für engl. Reachability.
* Die Abkürzung STCON steht für engl. s-t-Connectivity und bezeichnet das Erreichbarkeitsproblem in einem gerichteten Graphen. In dieser Variante ist es ein NL-vollständiges Problem.
* Die Abkürzung USTCON steht für engl. undirected s-t-Connectivity und bezeichnet das Erreichbarkeitsproblem in einem ungerichteten Graphen. In dieser Variante ist es ein L-komplexes Problem. Es lässt sich beispielsweise mit Hilfe der Breitensuche oder der Tiefensuche lösen. (de)
- In computer science, st-connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s. Formally, the decision problem is given by PATH = {⟨D, s, t⟩ | D is a directed graph with a path from vertex s to t}. (en)
- In informatica, la st-connectivity (o STCON) è il problema decisionale che consiste nel verificare se, dati due vertici e di un grafo orientato, è raggiungibile da . (it)
- Em ciência da computação e teoria da complexidade computacional, conectividade st é um problema de decisão onde dados os vértices s e t de um grafo direcionado, questiona-se se t é acessível partindo de s. Formalmente, o problema de decisão é dada por PATH = {⟨D, s, t⟩ | D é um grafo direcionado com um caminho do vértice s para outro vértice t}. (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)