𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Revised Greedy algorithm for formation of a minimal cycle basis of a graph

✍ Scribed by Kaveh, A. ;Roosta, G. R.

Publisher
John Wiley and Sons
Year
1994
Tongue
English
Weight
356 KB
Volume
10
Category
Article
ISSN
1069-8299

No coin nor oath required. For personal study only.

✦ Synopsis

SUM MARY

An efficient algorithm is developed for the formation of a minimal cycle basis of a graph. This method reduces the number of cycles to be considered as (candidates for being the elements of a minimal basis and makes practical use of the Greedy algorithm feasible. A comparison is made between the existing methods and the present algorithm. A counter-example is presented for Kaveh's algorithm from planar graphs.

Generalizing Kruskal's theorem, Rado, ' Edmonds and Welsh, ' independently, developed an algorithm for the formation of a minimal base of a matroid, known as the Greedy algorithm (see Whitney8 for the definition of a matroid in his pioneering paper on this subject). Kaveh' employed this algorithm for selecting, a minimal cycle basis of a graph using the set of simple cycles of a graph. A similar application has been suggested by Cassell el af.,"

πŸ“œ SIMILAR VOLUMES

The longest cycle of a graph with a larg
The longest cycle of a graph with a large minimal degree
✍ Noga Alon πŸ“‚ Article πŸ“… 1986 πŸ› John Wiley and Sons 🌐 English βš– 214 KB πŸ‘ 1 views

We show that every graph G on n vertices with minimal degree at least n / k contains a cycle of length at least [ n / ( k -111. This verifies a conjecture of Katchalski. When k = 2 our result reduces t o the classical theorem of Dirac that asserts that if all degrees are at least i n then G is Hamil

Subminimal cycle basis of a graph for ef
Subminimal cycle basis of a graph for efficient force method of frame analysis
✍ Kaveh, A. ;Moez, H. πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 135 KB πŸ‘ 1 views

A new method is presented for the formation of subminimal cycle bases of graphs corresponding to sparse exibility matrices. In this approach, a contraction method is used, leading to the reduction of the size of the graph at each step. This reduction facilitates the selection of the smallest cycle a

A Tight Analysis of the Greedy Algorithm
A Tight Analysis of the Greedy Algorithm for Set Cover
✍ Petr Slavı́k πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 214 KB

We establish significantly improved bounds on the performance of the greedy algorithm for approximating set co¨er. In particular, we provide the first substantial Ž . improvement of the 20-year-old classical harmonic upper bound, H m , of Johnson, Lovasz, and Chvatal, by showing that the performance

Minimizer graphs for a class of extremal
Minimizer graphs for a class of extremal problems
✍ Dan Ismailescu; Dan Stefanica πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 93 KB πŸ‘ 2 views

## Abstract We consider the family of graphs with a fixed number of vertices and edges. Among all these graphs, we are looking for those minimizing the sum of the square roots of the vertex degrees. We prove that there is a unique such graph, which consists of the largest possible complete subgraph