| 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 |
66425729 (xsd:integer) |
| dbo:wikiPageLength |
9409 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1039490644 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbc:Graph_connectivity dbr:Approximation_algorithm dbr:Depth-first_search dbr:Connected_graph dbr:Cross_bracing dbr:Linear_time dbc:Directed_graphs dbr:Directed_graph dbr:Strongly_connected_component dbr:Fixed-parameter_tractable dbr:Bipartite_graph dbc:Computational_problems_in_graph_theory dbr:Directed_acyclic_graph dbr:Grid_bracing dbr:Approximation_ratio dbr:Graph_algorithm dbr:Parameterized_complexity dbr:Square_grid dbr:Strongly_connected_graph |
| dbp:author2Link |
Robert Tarjan (en) |
| dbp:cs1Dates |
ly (en) |
| dbp:date |
January 2021 (en) |
| dbp:first |
Robert (en) Kapali (en) |
| dbp:last |
Eswaran (en) Tarjan (en) |
| dbp:wikiPageUsesTemplate |
dbt:Harvtxt dbt:R dbt:Reflist dbt:Use_dmy_dates dbt:Use_list-defined_references dbt:Harvs |
| dbp:year |
1976 (xsd:integer) |
| dct:subject |
dbc:Graph_connectivity dbc:Directed_graphs dbc:Computational_problems_in_graph_theory |
| 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 |
wikidata:Strong connectivity augmentation dbpedia-ru:Strong connectivity augmentation https://global.dbpedia.org/id/FmsTz |
| prov:wasDerivedFrom |
wikipedia-en:Strong_connectivity_augmentation?oldid=1039490644&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Strong_connectivity_augmentation |
| is dbo:wikiPageWikiLink of |
dbr:Incidence_and_Symmetry_in_Design_and_Architecture dbr:Strongly_connected_component dbr:Grid_bracing |
| is foaf:primaryTopic of |
wikipedia-en:Strong_connectivity_augmentation |