Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 James Waldby Posts: 308 Registered: 1/27/11
Re: Edge covering in graph
Posted: Jan 5, 2014 12:26 PM

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.
>> 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
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

Date Subject Author
1/5/14 James Waldby
1/5/14 steeve.beroard@gmail.com