Return to search

A primal-dual algorithm for the maximum charge problem with capacity constraints

In this thesis, we study a variant of the maximum cardinality matching problem known as
the maximum charge problem. Given a graph with arbitrary positive integer capacities assigned
on every vertex and every edge, the goal is to maximize the assignment of positive
feasible charges on the edges obeying the capacity constraints, so as to maximize the total
sum of the charges. We use the primal-dual approach. We propose a combinatorial algorithm
for solving the dual of the restricted primal and show that the primal-dual algorithm
runs in a polynomial time. / ix, 96 leaves : ill. ; 29 cm

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:ALU.w.uleth.ca/dspace#10133/2557
Date January 2010
CreatorsBhattacharjee, Sangita, University of Lethbridge. Faculty of Arts and Science
ContributorsGaur, Daya, Hossain, Shahadat
PublisherLethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2010, Arts and Science, Department of Mathematics and Computer Science
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
Languageen_US
Detected LanguageEnglish
TypeThesis
RelationThesis (University of Lethbridge. Faculty of Arts and Science)

Page generated in 0.0027 seconds