Back to search

Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2010

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

Abstract

dc:description.abstract

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.

Degree

thesis:*
Level thesis:degree_level
Masters
Grantor dc:publisher
Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2010
Year dc:date.issued
2010

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Bhattacharjee, Sangita
  • University of Lethbridge. Faculty of Arts and Science
Advisors dc:contributor.supervisor
  • Gaur, Daya
  • Hossain, Shahadat

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/2557

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Bhattacharjee, Sangita; University of Lethbridge. Faculty of Arts and Science. A primal-dual algorithm for the maximum charge problem with capacity constraints. Masters thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2010, 2010. https://hdl.handle.net/10133/2557