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

dc.contributor.authorBhattacharjee, Sangita
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorGaur, Daya
dc.contributor.supervisorHossain, Shahadat
dc.date.accessioned2011-11-09T23:28:14Z
dc.date.available2011-11-09T23:28:14Z
dc.date.issued2010
dc.degree.levelMasters
dc.descriptionix, 96 leaves : ill. ; 29 cmen_US
dc.description.abstractIn 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.en_US
dc.identifier.urihttps://hdl.handle.net/10133/2557
dc.language.isoen_USen_US
dc.publisherLethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2010en_US
dc.publisher.departmentDepartment of Mathematics and Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectMatching theoryen_US
dc.subjectCombinatorial optimizationen_US
dc.subjectGraph theoryen_US
dc.subjectDissertations, Academicen_US
dc.titleA primal-dual algorithm for the maximum charge problem with capacity constraintsen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
BHATTACHARJEE_SANGITA_MSC_2010.pdf
Size:
694.74 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.63 KB
Format:
Item-specific license agreed upon to submission
Description: