We show that for any $\epsilon > 0$, a maximum-weight triangle in an undirected graph with $n$ vertices and real weights assigned to vertices can be found in time $\O(n^{\omega} + n^{2 + \epsilon})$, where $\omega $ is the exponent of fastest matrix multiplication algorithm. By the currently best bound ... more >>>

We present two new methods for finding a lowest common ancestor (LCA) for each pair of vertices of a directed acyclic graph (dag) on n vertices and m edges. The first method is a natural approach that solves the all-pairs LCA problem for the input dag in time O(nm). The ... more >>>

We consider the ``minor'' and ``homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest $h$ such that the input graph has a minor isomorphic to $K_h$ or a subgraph homeomorphic to $K_h,$ respectively.We show the former to be approximable within $O(\sqrt {n} \log^{1.5} n)$ by ... more >>>

The Max-Bisection and Min-Bisection are the problems of finding partitions of the vertices of a given graph into two equal size subsets so as to maximize or minimize, respectively, the number of edges with exactly one endpoint in each subset. In this paper we design the first polynomial time approximation ... more >>>

The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree $k$-regular graphs for $3\le k\le 8,$ ... more >>>