 | | From: | les_ander at yahoo.com | | Subject: | bound on number of shortest paths in a undirected & unweighted graph | | Date: | 18 Jan 2005 08:03:11 -0800 |
|
|
 | Hi,
Is there are result that bounds the number of shortest paths between
any two nodes in a undirected && unweighted graph?
thanks
|
|
| | From: | sandey | | Subject: | Re: bound on number of shortest paths in a undirected & unweighted graph | | Date: | 19 Jan 2005 03:43:37 -0800 |
|
|
| Interestingly ,the concept of a bound depending on the degree of the
graph. is not possible as shown before (i mean the example used by
david to demonstrate that there can be infinite such paths), although
the representation of all such paths can be done in polynomial time.
By representation, i mean a structure from which, (given a polynomial
length {polynomial in the graph's size} certificate), i can compute a
path satisfying that certificate. The definition is vague, since the
certificate can anything.
I am sorry this definition is so vague, but I guess , what i am trying
to find a structure, which given a few parameters/charectistics more
about the set of solutions, outputs the solution in polynomial
time.(This can also be implemented in the algorithm in the first place
itself but more precisely I would like to discuss about a structure and
not an algorithm)
Sandeep Dey,
PS: sorry if the reply is very vague :)
David Wagner wrote:
> >Is there are result that bounds the number of shortest paths between
> >any two nodes in a undirected && unweighted graph?
>
> Did you see my previous post? I showed that there could be
exponentially
> many simple paths. (Obviously there can't be a super-exponential
number of
> simple paths.) It is also clear that there could be as few as zero
simple
> paths. Therefore, the best possible bounds are zero and
exponentially many.
>
> If you allow non-simple paths (paths that follow a cycle multiple
times,
> for instance), then there could be anywhere between zero and
infinitely
> many paths.
>
> Did you want something tighter than this? What exactly are you
looking for?
|
|
| | From: | David Wagner | | Subject: | Re: bound on number of shortest paths in a undirected & unweighted graph | | Date: | Thu, 20 Jan 2005 00:35:12 +0000 (UTC) |
|
|
| sandey wrote:
>By representation, i mean a structure from which, (given a polynomial
>length {polynomial in the graph's size} certificate), i can compute a
>path satisfying that certificate. The definition is vague, since the
>certificate can anything.
Impossibly vague. What do you mean by a certificate? I'm sorry, but
I can't tell what you are asking or what you really want. You'll have
to define the notion of a certificate first, and what it means to say
that a particular path P satisfies a particular certificate C.
Hint: Is the graph itself an acceptable representation? If not, why not?
Until you can answer those questions, you don't have a precise enough
definition of "certificate".
|
|
| | From: | lorber_sean2002 at yahoo.com | | Subject: | Re: bound on number of shortest paths in a undirected & unweighted graph | | Date: | 19 Jan 2005 19:56:37 -0800 |
|
|
| David wrote:
If you allow non-simple paths (paths that follow a cycle multiple
times,
for instance), then there could be anywhere between zero and infinitely
many paths.
Sean wrote:
When would paths cycle multiple times? Are you referring to wait
times?
|
|
| | From: | lorber_sean2002 at yahoo.com | | Subject: | Re: bound on number of shortest paths in a undirected & unweighted graph | | Date: | 20 Jan 2005 21:38:11 -0800 |
|
|
| I don't think negative weights could effect how many equally short
paths there are.
|
|
| | From: | sandey | | Subject: | Re: bound on number of shortest paths in a undirected & unweighted graph | | Date: | 20 Jan 2005 03:53:38 -0800 |
|
|
|
David Wagner wrote:
> Impossibly vague. What do you mean by a certificate? I'm sorry, but
> I can't tell what you are asking or what you really want. You'll
have
> to define the notion of a certificate first, and what it means to say
> that a particular path P satisfies a particular certificate C.
I am sorry for the vague definitions. I was talkig about advice
functions, but it turned out that you dont have to think that far.
Thanks
Sandeep Dey
|
|
| | From: | sandey | | Subject: | Re: bound on number of shortest paths in a undirected & unweighted graph | | Date: | 20 Jan 2005 03:43:47 -0800 |
|
|
| > Sean wrote:
> When would paths cycle multiple times? Are you referring to wait
> times?
That problem wont come in here because of this being a unweighted
graph. That problem will only come if u have a cycle of weight 0, and
that implies presence of negative weights. For cycles with -ve weight,
there wont exist any shortest paths :)
Hope that helps
Sandeep Dey
|
|
| | From: | David Wagner | | Subject: | Re: bound on number of shortest paths in a undirected & unweighted graph | | Date: | Wed, 19 Jan 2005 04:02:26 +0000 (UTC) |
|
|
| >Is there are result that bounds the number of shortest paths between
>any two nodes in a undirected && unweighted graph?
Did you see my previous post? I showed that there could be exponentially
many simple paths. (Obviously there can't be a super-exponential number of
simple paths.) It is also clear that there could be as few as zero simple
paths. Therefore, the best possible bounds are zero and exponentially many.
If you allow non-simple paths (paths that follow a cycle multiple times,
for instance), then there could be anywhere between zero and infinitely
many paths.
Did you want something tighter than this? What exactly are you looking for?
|
|
