All reports by Author Venkatesh Raman:

__
TR02-031
| 30th April 2002
__

Vikraman Arvind, Venkatesh Raman#### Approximate Counting small subgraphs of bounded treewidth and related problems

Revisions: 1

__
TR97-033
| 1st August 1997
__

Meena Mahajan, Venkatesh Raman#### Parametrizing Above Guaranteed Values: MaxSat and MaxCut

Vikraman Arvind, Venkatesh Raman

We give a randomized approximation algorithm taking

$O(k^{O(k)}n^{b+O(1)})$ time to count the number of copies of a

$k$-vertex graph with treewidth at most $b$ in an $n$ vertex graph

$G$ with approximation ratio $1/k^{O(k)}$ and error probability

inverse exponential in $n$. This algorithm is based on ...
more >>>

Meena Mahajan, Venkatesh Raman

In this paper we investigate the parametrized

complexity of the problems MaxSat and MaxCut using the

framework developed by Downey and Fellows.

Let $G$ be an arbitrary graph having $n$ vertices and $m$

edges, and let $f$ be an arbitrary CNF formula with $m$

clauses on $n$ variables. We improve ...
more >>>