TAILIEUCHUNG - Finding minimal branchings with a given number of arcs

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 asymetric 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. | Yugoslav Journal of Operations Research 12 (2002), Number 1, 1-10 FINDING MINIMAL BRANCHINGS BRANCHINGS WITH A GIVEN NUMBER OF ARCS Drago{ CVETKOVI] Faculty of Electrical Engineering University of Belgrade, Belgrade, Yugoslavia Mirjana ^ANGALOVI] Faculty of Organizational Sciences University of Belgrade, Belgrade, Yugoslavia Abstract: 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 asymetric 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. Key words: Combinatorial optimization, weighted graphs, minimal branching. 1. INTRODUCTION We consider an arc weighted digraph G without loops and with an asymmetric weight matrix. As usual, the weight d ( H ) of any subgraph H of G is defined to be the sum of weights of arcs of H . We start with some specific definitions. Definition 1. A tree in which each edge is directed (so that it becomes an arc) is called a directed tree. tree Definition 2. A directed tree is called an arborescence if the following conditions are fulfilled: 1. There is a node x with no entering arcs; 2. Exactly one arc enters each of the other nodes. Node x is called the root. root 2 D. Cvetkovi}, M. ^angalovi} / Finding Minimal Branchings with a Given Number of Arcs Definition 3. A digraph whose weakly connected components are arborescences is called a branching. branching. branching A branching with s arcs is called an s -branching branching We consider the problem of finding a minimal s -branching in G , . a branching with minimal weight. An algorithm for this problem has been developed in [6] (see also [8], pp. 59-61) and we describe it here. The algorithm uses the basic principles of a method for determining a minimal branching .

• Kinh tế học
• Combinatorial optimization
• Weighted graphs
• Minimal branching
• Asymetric weight matrix
• Minimal s branching
• Ecosystem management
• Combinatorial optimization techniques
• Meta heuristic
• Economical values
• Probabilistic Combinatorial Optimization
• Probabilistic Graph problems
• Probabilistic Minimum Coloring
• The Probabilistic Longest Path
• Probabilistic Minimum Vertex
• the Probabilistic Maximum Independen
• Efficient transformations
• Generalized combinatorial optimization problems
• Integer programming
• Graph into node sets
• Extremal graph theory
• Variable neighborhood search
• Mathematical programming
• Efficient algorithms
• Information sciences
• Multiobjective combinatorial optimization problems
• Well spread set
• Well spread non dominated points
• State of the art
• Ebook Linear optimization
• Linear optimization
• Linear extensions
• Projective algorithms
• Ellipsoid algorithms
• Optimization software
• Minimum cost network flow problem
• Optimization software packages
• Meta–Heuristic methods
• Swarm intelligence
• Scheduling problems
• Foraging habits of honeybees
• Center location problems
• Reverse optimization
• Tree graphs
• Time complexity
• Hamming norms
• Gaussian variable neighborhood search
• File transfer scheduling problem
• Optimization problems
• Báo cáo sinh học hay
• cách trình bày báo cáo
• báo cáo sinh học
• công trình nghiên cứu sinh học
• tài liệu về sinh học
• Dynamic memory allocation Ppblem
• Regarding quality
• Metaheuristic approach
• Transportation problem
• Bottleneck transportation problem
• Bi criteria transportation problem
• Efficient points
• Salesman problem
• System of vertexr equisitions
• Local search
• Efficient point
• Evolutionary algorithms
• Runtime analysis
• Fitness level
• Strong metric dimension
• Graph problems
• Computational approaches
• Historical and scientific framework
• Music generation
• Evolutionary approach
• Algorithm composing
• Music compositions
• Genetic Algorithm
• Optimal Recombination Problem
• Boolean Linear Programming
• Optimal recombination
• Maximum Diverse Grouping
• Extensive computational
• Diversity problem
• Operations research
• Exteriorpoint simplex type
• Network dual simplex algorithm
• Electromagnetism like metaheuristic
• Maximum set splitting problem
• Steiner triple systems
• Fast implementation
• Evolutionary computation
• Graph coloring problem
• Bandwidth multicoloring problem
• Bandwidth coloring problem
• Quadratic assignment problem
• Modified genetic operators