Abstracts


 
 

Improved Algorithms for Replacement Paths Problems in Restricted Graphs
Amit M. Bhosle


     We study the following two problems related to finding the replacement paths for edges with respect to shortest paths in sparse graphs.
   (1) Given an undirected weighted graph $G(V,E)$, two nodes $s$ and $t$, let the shortest path from $s$ to $t$ be $\mathcal{P}_{s,t} = \{e_1, e_2,...,e_k\}$. Compute the shortest $s$-$t$ path in each of the $k$ graphs $G(V,E\setminus e_i)$ for $1 \leq i\leq k$.
   (2) Given an undirected weighted graph $G(V,E)$, let the shortest paths tree of node $s$ be $\mathcal{T}_s = \{e_1,e_2,...,e_{n-1}\}$, where $e_i = (x_i,y_i)$ and $x_i = parent_{\mathcal{T}_s}(y_i)$ is the parent of $y_i$ in $\mathcal{T}_s$. Compute the shortest path from $y_i$ to $s$ in the graph $G(V,E\setminus e_i)$ for $1\leq i\leq n-1$.
   We present (near) linear-time algorithms for these problems which employ a new technique of using Minimum Spanning Trees in these shortest paths problems.


[Back]

Replacement Paths for Pairs of Shortest Path Edges in Directed Graphs
Amit M. Bhosle, Teofilo F. Gonzalez


     The (Single-Edge) Replacement Paths problem is defined as follows: Given a weighted graph $G(V,E)$, two nodes $s$ and $t$, and the shortest path $\mathcal{P}_{G}(s,t) = \{ e_1, e_2, \ldots, e_p \}$ from $s$ to $t$ in $G$, compute the shortest path from $s$ to $t$ in the graph $G\backslash e_i$ for $1\leq i\leq p$. In other words, the single-edge replacement paths problem studies how a given $s$-$t$ shortest path changes with the deletion of an edge lying on the path. We study a two-edge generalization of this problem for directed graphs, termed the Edge Pairs Replacement Paths problem: Given $G$, $s$, $t$, and $\mathcal{P}_G(s,t)$ as defined above, compute the shortest path from $s$ to $t$ when two edges of $\mathcal{P}_{G}(s,t)$ fail, for all the $p^2$ pairs of edges of $\mathcal{P}_G(s,t)$. We present an $O(n^3)$ algorithm for this problem, and establish an $\Omega(mn)$ lower bound in the path comparison model for shortest path algorithms which was introduced in $\cite{kkp}$.
     Our algorithm is based on a new algorithm for the directed version of the single-edge replacement paths problem which makes clever use of the information provided by the all-pairs-shortest-paths computation on a modification of the input graph and avoids extensive recomputations required by the naive algorithm.


[Back]

Exact and Approximation Algorithms for Finding the Optimal Bridge Connecting Two Simple Polygons
Amit M. Bhosle, Teofilo F. Gonzalez


     Given two simple polygons $P$ and $Q$ we define the weight of a bridge $(p,q)$, with $p\in \rho(P)$ and $q\in \rho(Q)$, where $\rho()$ defines the compact region enclosed by the boundary of the polygon, between the two polygons as $gd(p,P) + d(p,q) + gd(q,Q)$, where $d(p,q)$ is the Euclidean distance between the points $p$ and $q$, and $gd(x,X)$ is the geodesic distance between $x$ and its geodesic furthest neighbor on $X$. Our problem differs from another version of the problem where the additional restriction of requiring the endpoints of the bridge to be mutually visible was imposed. We show that an optimal bridge always exists such that the endpoints of the bridge lie on the boundaries of the two polygons. Using this critical property, we present an algorithm to find an optimal bridge (of minimum weight) in $O(n^2 \log n)$ time. We also present a polynomial approximation scheme that, given any positive integer $k$, constructs a bridge with objective function value within $(1 + \frac{2}{k+1})$ of optimal in $O(kn \log kn)$ time. We also present a polynomial time approximation scheme that for any $\epsilon >0$ generates a bridge with objective function within $\epsilon$ of optimal in $O(kn \log kn)$ time, where $k = 2*\lceil \frac{1}{\log (1+\epsilon)} \rceil$. Algorithms for generalized versions of our problems are also discussed.
 

[Back]

Algorithms for Single Link Failure Recovery and Related Problems
Extended version of Efficient Algorithms for Single Link Failure Recovery and Its Applications to ATM Networks
Amit M. Bhosle, Teofilo F. Gonzalez


     We investigate the single link failure recovery problem and its application to the alternate path routing problem for ATM networks, and the $k$-replacement edges for each edge of a minimum cost spanning tree. Specifically, given a 2-connected graph $G$, a specified node $s$, and a shortest paths tree $\mathcal{T}_s = \{ e_1,$ $e_2,$ $\ldots,$ $e_{n-1} \}$ of $s$, where $e_i = (x_i,y_i)$ and $x_i=parent_{\mathcal{T}_s}(y_i)$, find a shortest path from $y_i$ to $s$ in the graph $G\backslash e_i$ for $1\leq i\leq n-1$. We present an $O(m+n\log n)$ time algorithm for this problem and a linear time algorithm for the case when all weights are equal. When the edge weights are integers, we present an algorithm that takes $O(m+T_{sort}(n))$ time, where $T_{sort}(n)$ is the time required to sort $n$ integers. We establish a lower bound of $\Omega(min(m\sqrt{n},n^2))$ for the {\rm directed\footnote{In the directed version, $\mathcal{T}_s$ is the shortest paths {\em destination} tree of $s$.}} version of our problem under the path comparison model. We show that any solution to the single link recovery problem can be adapted to solve the alternate path routing problem in ATM networks. Our technique to solve the single link failure recovery problem is adapted to find the $k$-replacement edges for the tree edges of a minimum cost spanning tree in $O(m + n \log n)$ time.

[Back]

On the Difficulty of Some Shortest Path Problems
John Hershberger , Subhash Suri, Amit M. Bhosle


     We prove super-linear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem: Given a directed graph $G$ with non-negative edge weights, and a shortest path $P = \{e_1, e_2, \ldots, e_p \}$ between two nodes $s$ and $t$, compute the shortest path distances from $s$ to $t$ in each of the $p$ graphs obtained from $G$ by deleting one of the edges $e_i$. We show that the replacement paths problem requires $\Omega(m\sqrt{n})$ time in the worst case whenever $m=O(n\sqrt{n})$. This also establishes a similar lower bound for computing the \emph{second shortest} simple path by any algorithm that uses replacement paths as a subroutine; all known algorithms for the $k$ shortest paths fit this description. To put our lower bound in perspective, we note that both these problems (replacement paths and second shortest path) can be solved in near linear time for undirected graphs. We also give a nearly tight lower bound of $\Omega (nm)$ for computing the shortest path distances between a fixed source $s$ and all other nodes if each edge of the shortest path tree is removed in turn.


[Back]

Optimal Assignment of High Threshold Voltage for Synthesizing Dual Threshold CMOS Circuits
Nikhil Tripathi, Amit M. Bhosle, Debasis Samanta, Ajit Pal



     Development of the process technology for dual threshold (dual $V_{th}$) CMOS circuit has opened up the possibility of using it to reduce static power in low voltage high performance circuits. It has been demonstrated that by using transistors of a low threshold voltage for gates on the critical path, and by using a high threshold for gates in the off-critical path it is possible to significantly reduce leakage power consumption of a circuit without performance degradation. In this paper we have proposed a new algorithm to realize dual threshold CMOS circuits. Our algorithm produces significantly better results for the ISCAS benchmark circuits compared to the reported results.
 


[Back]