OJ Board

Hi

Please give in your ideas and suggestions on the following problems on approximation algorithms:

1)Give an approximation algorithm that takes an instance of the knapsack problem and a positive integer k and returns a packing with an approximation ratio of no more than 1 + 1/k . Your algorithm ...

Hello everyone,

Please give in your ideas and suggestions to this problem:

Given a directed graph G = (V,E) and a positive integer
k, we wish to determine whether there is a subset V ? ? V of size k such that
every cycle in G contains at least one vertex in V ?. Show that this problem
is NP ...

thanks for the replies

hi all
when talking in term of trees/graphs:
1)what is meant by pre-processing an edge and pre-processing a vertex?(The context in which this is mentioned is Depth First Search)
2)What is the definition of a depth first spanning forest?
3)What are the requirements for a vertex to be an articulation ...

Hello all,

Problem :

We are given two arrays of integers, R[1..m] and C[1..n]
such that R[1]+R[2]+...+R[m]=C[1]+C[2]+..+C[n]=k.
Give an O(kmn) algorithm that returns an m× n matrix of 0s and 1s such
that row i contains exactly R 1s and column j contains exactly C[j] 1s,
for all 1 ? i ? m and 1 ? j ...

thanks for the reply
i am sorry for the spellings.


Can you please suggest something for this problem:

A path cover of a directed graph is a set of paths such
that every vertex is included in exactly one path. The size of a path cover is
the number of paths in the set. Show how to reduce the ...

Hello all

Plz give ur ideas n suggestions:

We define an n × n grid to be an undirected graph (V,E)
where V = {(i, j) | 1 ? i ? n, 1 ? j ? n}, and two vertices (i, j) and (i?, j?)
are adjacent iff either i = i? and j = j?±1 or j = j? and i = i?±1. Thus, each
vertex in a grid has at most 4 neighbors ...

thx for the reply
yes i have to read that chapter

I just wanted to seek an explanation to the following code to find the number of bridges in an undirected,connected graph:
What is the use of the low array here?

int low[MAXN], seen[MAXN], counter;

void dfs(int x, int parent)
{
low[x] = seen[x] = ++counter;

for each edge x->y
{
if (y ...