On strongly connected digraphs with bounded cycle length (Q1923587)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 933102
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On strongly connected digraphs with bounded cycle length |
scientific article; zbMATH DE number 933102 |
Statements
On strongly connected digraphs with bounded cycle length (English)
0 references
7 April 1997
0 references
Let \(G\) be a strongly connected digraph with cycles of length 3 or less. We wish to find a strongly connected spanning subgraph of \(G\) with the least number of edges. The authors show that this problem is equivalent to the minimum bipartite edge cover problem. This equivalence allows the authors to improve the performance of the best approximation algorithm to the general problem with no cycle bounds.
0 references
maximum matching
0 references
strongly connected digraph
0 references
minimum bipartite edge cover
0 references
approximation algorithm
0 references
cycle
0 references
0.7907469868659973
0 references
0.7792577147483826
0 references
0.7656602263450623
0 references
0.7652105689048767
0 references
0.7622580528259277
0 references
