From: "al" <andyleeNOSPAM@NOHAM.ihub.clara.co.uk>
Subject: Re: Similar to stacker crane problem in graph theory?
Date: Thu, 1 Jun 2000 00:20:44 +0100
Newsgroups: sci.math
Summary: [missing]

Hi Julio,

> I don't know the "Stacker Crane Problem".  Will you please be so kind to
> state it?

To be more specific, the Minimum Stacker Crane Problem is as follows:

For a mixed graph G=(V, A, E), all arc/edge lengths have positive weights,
MSCP problem
is to find cycle in G (possibly containing repeated vertices) that includes
each directed edge in
A at least once, traversing edges in the specified direction. The solution
to MSCP is cycle with
the minimum total length.

I've scoured the NP optimization compendium located at
http://www.nada.kth.se/theory/problemlist.html
to see if I can identify an existing NP-complete problem in the literature
that is similar to the one I have.

The problem I stated seems to be similar to the MSCP problem but a less
cursory examination that MSCP will yield
a tour of all edges but may not produce a tour of all nodes (which I
require). So my problem it's not MSCP.

> I think this problem (as I understand it) is equivalent to "Travelling
> Salesman Problem", which has lots of stuff devoted to.

Now I know it is a variant of a Travelling Salesman Problem as I require a
minimum cost tour
(in terms of edge costs) which visits each node in G at least once. The TSP
is somewhat relaxed as I can traverse
a node and arc more than once as long as I visit every node. I think my
problem may be simpler than I think :)

> The way to do this is building a complete graph with the same vertex set
> and edges weight equal to
> the distance (in number of edges) of its extreme vertices in the original
> graph.

I'm not sure what you mean by extreme vertices. Can you clarify?

Cheers,

Andy