Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



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 >> >xyplane? >> >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



