From: Oliver Kullmann (O.Kullmann_at_[hidden])
Date: 2005-12-07 11:31:41
On Wed, Dec 07, 2005 at 09:38:28AM -0500, Douglas Gregor wrote:
> On Dec 6, 2005, at 1:59 PM, Michael Drexl wrote:
> > is there any interest in including an algorithm for solving the
> > shortest
> > path problem with resource constraints (SPPRC) in the Boost Graph
> > library?
I would second it; many more algorithms are needed.
> > I've implemented an exact algorithm for this NP-hard problem. The
> > algorithm is basically a label-setting algorithm based on dynamic
> > programming. It is parameterized on the graph type (of course) and the
> > type of the resource container (data structures specifying what
> > resources there are and how they are to be managed in the course of
> > the
> > algorithm).
For such hard problems there is an enormous design space (and an even
bigger algorithm space) to be considered, so a good dose of genericity
in the implementation would be appreciated (hopefully it comes with
Since it's NP-hard, it would be good to have also a reduction from
some well-known NP-complete problem to SPPRC (for example graph
colouring), which would be very useful for testing (using some
established implementation for that NP-complete problem).
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk