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

Re: "task" and beyond

On Wed, Feb 05, 2003 at 11:12:41PM +0900, Oohara Yuuma wrote:
> On Wed, 5 Feb 2003 03:29:22 -0800,
> Osamu Aoki <osamu@debian.org> wrote:

>> (dependency check is N^2 problem and started to stress system
>> badly.)

> If someone implements an algorithm which splits a given set of
> packages into 2 sets A and B so that no package in A depends on any
> package in B and no package in B depends on any package in A,
> dependency check can be a NlogN problem.

This looks impossible to me: I conjecture that by walking the
dependency graph from any package, you'll end up in libc; the
(non-oriented) dependency graph is connected.


Reply to: