| dbo:abstract
|
- Strong connectivity augmentation is a computational problem in the mathematical study of graph algorithms, in which the input is a directed graph and the goal of the problem is to add a small number of edges, or a set of edges with small total weight, so that the added edges make the graph into a strongly connected graph. The strong connectivity augmentation problem was formulated by Kapali Eswaran and Robert Tarjan. They showed that a weighted version of the problem is NP-complete, but the unweighted problem can be solved in linear time. Subsequent research has considered the approximation ratio and parameterized complexity of the weighted problem. (en)
- Дополнение графа до сильно связного ― вычислительная задача теории графов, входными данными для которой является ориентированный граф. Цель задачи ― добавить минимальное число дуг (или множество дуг с минимальным суммарным весом) так, чтобы исходный граф стал сильно связным. Задача о дополнении графа до сильно связного была сформулирована Эсвараном Капали и Робертом Тарьяном в 1976 году. Они доказали, что взвешенная версия задачи является NP-полной, а невзвешенная версия может быть решена за линейное время. Дальнейшее исследование задачи позволило найти приближённый алгоритм и параметризованную сложность для взвешенной версии. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9409 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:author2Link
| |
| dbp:cs1Dates
| |
| dbp:date
| |
| dbp:first
| |
| dbp:last
| |
| dbp:wikiPageUsesTemplate
| |
| dbp:year
| |
| dcterms:subject
| |
| rdfs:comment
|
- Strong connectivity augmentation is a computational problem in the mathematical study of graph algorithms, in which the input is a directed graph and the goal of the problem is to add a small number of edges, or a set of edges with small total weight, so that the added edges make the graph into a strongly connected graph. (en)
- Дополнение графа до сильно связного ― вычислительная задача теории графов, входными данными для которой является ориентированный граф. Цель задачи ― добавить минимальное число дуг (или множество дуг с минимальным суммарным весом) так, чтобы исходный граф стал сильно связным. (ru)
|
| rdfs:label
|
- Strong connectivity augmentation (en)
- Дополнение графа до сильно связного (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
