Finding minimal branchings with a given number of arcs | Zendy

Dragoš Cvetković | Zendy; Mirjana Čangalović | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Finding minimal branchings with a given number of arcs

Author(s) -

Dragoš Cvetković,

Mirjana Čangalović

Publication year - 2002

Publication title -

yugoslav journal of operations research

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.221

H-Index - 21

eISSN - 1820-743X

pISSN - 0354-0243

DOI - 10.2298/yjor0201001c

Subject(s) - correctness , digraph , mathematics , branching (polymer chemistry) , combinatorics , algorithm , discrete mathematics , computer science , materials science , composite material

We describe an algorithm for finding a minimal s-branching (where s is a given number of its arcs) in a weighted digraph with an a symetric weight matrix. The algorithm uses the basic principles of the method (previously developed by J. Edmonds) for determining a minimal branching in the case when the number of its arcs is not specified in advance. Here we give a proof of the correctness for the described algorithm

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research