On Wed, Feb 12, 2003 at 02:58:32PM +0100, Lionel Elie Mamane wrote: > 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. Then you could split the packages into three groups, A, B and C so that A and B depend on C but not on eachother (say KDE, Gnome and libc). Unfortunatly I have no idea whether this helps at all. -- Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/ > Support bacteria! They're the only culture some people have.
Attachment:
pgpSqEzqqHrA5.pgp
Description: PGP signature