Date and Place





Tarikul Sabbir

An Algorithmic study of Tree Decomposition(and Tree Width) and it's

application on optimization problems

In graph theory, a tree decomposition of a graph is a measure of how much

a graph resembles a tree. And the treeWidth measures the number of graph

vertices mapped onto any tree node in an optimal tree decomposition. Many

NP-hard graph problems can be solved in polynomial time for graphs with

bounded/restricted treewidth. There are  Several heuristic algorithms to

find tree decompositions as well as tree-width. Some of heuristics are

discussed in detail. This tree decomposition technique can also be applied

to find (almost) optimal solutions for many optimization problems. In this

context a dynamic programming framework is used on tree

decompositions(under work in progress) of to solve facility location

optimization problems like P-median and Covering problem on the original

graphs. The time bound of the given algorithm is explained and on a

closing note the potential ideas for improving the time bound are also



Mahmudul Hasan

DSJM: A software toolkit for Direct Determination of Sparse Jacobian


Packing the nonzero elements of a sparse Jacobian matrix in fewer

column groups can gain significant performance improvement in Finite

Differencing and Forward Automatic Differentiation methods. If $B\in \Re^{m\times p}$ is obtained via finite difference approximation or forward automatic differentiation, we can directly determine the

jacobian $A\in \Re^{m\times n}$ using the partitioning matrix $S\in \Re^{n\times p}$, where $AS = B$, provided that the sparsity pattern of $A$ is a priori known. DSJM, a software toolkit written in C++, has been developed to provide some well-known as well as new partitioning

algorithms for large sparse matrices. The heuristic algorithms used in the software can be explained from a graph coloring point of

view. The relation of Zykov Tree with a coloring heuristic is also discussed.


Robert Benkoczi, Department of Mat/CS, University of Lethbridge

The parametric search method in optimization

Parametric search is an ingenious method to solve an optimization problem that generalizes the approach based on feasibility tests. For some optimization problems, a feasibility test is easier to solve since the test doesn't ask for the optimal solution to the problem, but whether the optimal solution is larger or smaller than a given test value. This presentation should be accessible to graduate and 3rd & 4th year undergraduate students.


Sangita Bhattacharjee

Graduate Student & Research Assistant

Department of Math & Computer Science

A Primal-Dual algorithm for Maximum-Charge Problem with capacity


Maximum charge problem is a generalization of Maximum Cardinality Matching Problem, a well known problem in graph theory. Given a graph with arbitrary positive capacities assigned on every vertex and every edge the goal is to maximize the total amount of charge on edges subject to the capacity constraints. We use the primal-dual approach for

the maximum charge problem. We characterize the optimal solution to the dual of the restricted primal(DRP)and give a combinatorial  algorithm for solving the DRP.