Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: Edge covering in graph
Replies: 3   Last Post: Jan 5, 2014 2:37 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
James Waldby

Posts: 308
Registered: 1/27/11
Re: Edge covering in graph
Posted: Jan 5, 2014 12:26 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Sun, 05 Jan 2014 06:38:23 -0800, Steeve Beroard wrote:
> Le dimanche 5 janvier 2014 10:48:25 UTC+1, quasi a écrit :
>> quasi wrote:
>> >Steeve Beroard wrote:
>> >>Given a graph with superposed edges between vertices, I'm
>> >>looking for a fast algorithm to determine if a given edge is
>> >>completely covered by a particular set of edges, where could
>> >>I look for this?


>> >By covered do you mean covered geometrically?
>> >Is the graph given by specified vertices and edges in the
>> >xy-plane?
>> >Can you give a simple example to illustrate the problem?

>> Ok, I see you just posted a corrected version.
>> Your original wording made little sense.
>> But still, an illustrative example would be helpful.


> If we suppose we are working with a graph similar to a binary
> tree with a single node per level, let's say we have 3 vertices
> A B C connected with each other in this order. if U is a vertex,
> let's call low(U) and high(U) the set of edges from the vertex
> U to the next one. From the data: low(A) = {1, 2}; high(A) =
> {1, 3}; low(B) = {1, 2, 3} ; high(B) = {1, 2, 3}. We can say
> that edge 1 is "covered" by 2 and 3 from A to C. Is there any
> algorithm to solve this lower than exponential in the general
> case?


In another post quasi has already asked what you mean by some
of the above. Anyhow, your example is unclear because you
don't tell us which nodes are connected by edges. Apparently
nodes A, B, C are connected, but "in this order" is ambiguous
and does not specify a unique set of edges. Does it mean there
is an undirected edge AB, and a second undirected edge BC ?
Or perhaps directed edges AB and BC ? Or directed edges AB,
BC, CA ?

Another reason the example is unclear is that it refers to
edges 1, 2, 3 without it having been said which vertices those
edges connect. Another reason is that low() and high() are
referred to as "the set of edges from the vertex U to the next
one" without spelling out how low() differs from high(). In
other words, you have not defined low() and high() or the
graph that is supposed to illustrate them, so the example is
unclear.

You also don't say whether edges are directed. Rather than
starting out with "Given a graph", instead start with one
of "Given a directed graph" or "Given an undirected graph".

Your original question refers to "superposed edges", which
in English could mean edges placed on top of other edges or
could mean edges added to a graph, regardless of whether an
edge was there before; so you will need to define that too,
as well as what you mean by "covered".

All that said, for at least one interpretation of your graph
and your question, there is an O(1) method. In other
interpretations, complexity looks like O(v+e) or O(e^3).

--
jiw



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.