[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

**To**:**"Aofa@Pommard.Inria.Fr (E-mail)" <Aofa@pommard.inria.fr>****Subject**:**Some cpmplexity problems****From**:**Yelena Shabtai <YelenaShabtai@imi-telecom.com>**- Date: Thu, 22 Apr 1999 12:04:48 +0200
- Content-Type: text/plain;charset="iso-8859-1"

Hello ! My name is Yelena. I am learning course "Complexity of the algorithms". I have some problem and don't know how to solve them. If you have time to help me I will very appreciate. Problem 1. T(N) - time of computation 2 matrices (A,B) of n*n S(N) - time of computation A of n in power 2 . Proof : T(n) = q(S(n)) AB <> BA Hint: Go to more big matrices Problem 2. Find algorithm for calculating max independent set in the graph in form of the tree. Computation time should be O(V). Hint: Tree has nodes with degree 1. Problem 3. P(K;G) - is chromatic number of graph. Proof : for graph with n nodes there is 0 <= s < n and number of ways for coloring the graph G can be described as sum of poloniums of the form K(K-1)(K-2)... (K-s). Thank in advance, Yelena

- Prev by Date:
**Set symmetric difference** - Next by Date:
**Fibonacci Heaps** - Prev by thread:
**Set symmetric difference** - Next by thread:
**Fibonacci Heaps** - Index(es):