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
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:ALU.w.uleth.ca/dspace#10133/2557 |
| Date | January 2010 |
| Creators | Bhattacharjee, Sangita, University of Lethbridge. Faculty of Arts and Science |
| Contributors | Gaur, Daya, Hossain, Shahadat |
| Publisher | Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2010, Arts and Science, Department of Mathematics and Computer Science |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
| Relation | Thesis (University of Lethbridge. Faculty of Arts and Science) |
Page generated in 0.0027 seconds