1
$\begingroup$

I'm not sure of the terminology. I define a list to be a path where every vertex along the path has precisely two edges, except possibly the starting and ending vertex. In the language of electric circuits, I'm interested in finding all components that are in series for a given circuit. Is there an efficient way of doing this?

My thoughts are something that seems too complex - start at an arbitrary vertex that has not yet been visited. If its degree is 2, then it lies on a list. Move along this list until you find a vertex that has degree 1 or degree > 2 (you've found the end of the list). Move back along the list, marking all vertices along it as visited, and writing down the nodes you've visited until you find the other end. Repeat until you're out of non-visited vertices.

On the other hand, if your initial vertex does not lie on a list, then it is potentially an end point of one. Check the degree of all vertices connected to it. For any of them that have degree 2, continue as above.

This seems drastically inefficient. Is there:

a) A term for such a thing? b) An efficient algorithm for finding them?

$\endgroup$
  • 1
    $\begingroup$ An interesting question perhaps better asked here: cstheory.stackexchange.com $\endgroup$ – Ethan Bolker Aug 7 '17 at 12:58
  • 1
    $\begingroup$ It seems like you are looking for the 'Ear decomposition'? en.wikipedia.org/wiki/Ear_decomposition $\endgroup$ – gilleain Aug 7 '17 at 13:04
  • $\begingroup$ That looks about right, thanks! $\endgroup$ – Michael Stachowsky Aug 7 '17 at 13:16
  • $\begingroup$ Cross-posted: math.stackexchange.com/q/2385540/14578, cs.stackexchange.com/q/79858/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Aug 8 '17 at 20:31
  • $\begingroup$ @EthanBolker, I know you're trying to help, but could I make a request for the future? When suggesting another site, could you please remind the person not to cross-post? You can suggest that they delete the copy here before posting it elsewhere. That will provide a better experience for everyone. Thank you for understanding! (And, to restate what is probably obvious, just because a question is "better" elsewhere doesn't make it unsuitable or off-topic here.) $\endgroup$ – D.W. Aug 8 '17 at 20:33

Browse other questions tagged or ask your own question.