Xref: utzoo comp.theory:1795 sci.math:16603
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!uunet!mstan!sethb
From: sethb@Morgan.COM (Seth Breidbart)
Newsgroups: comp.theory,sci.math
Subject: Re: Some questions about circuits in graphs
Message-ID: <2993@ylum.Morgan.COM>
Date: 10 Apr 91 17:10:21 GMT
References: <1991Apr9.161805.6764@irisa.fr>
Organization: Morgan Stanley, & Co., Inc. / New York City, NY
Lines: 17

In article <1991Apr9.161805.6764@irisa.fr> jeron@irisa.fr (jeron)
writes:
>I am looking for an algorithm (and not a naive one)
>of graph theory which deals with circuits in directed graphs.

>The question is:
>Given a directed graph G=(V,E) and a subset W of V,
>find an algorithm which tells whether every circuit of G contains
>at least one vertice w in W.


Why not just delete W from G, and check for circuits in the remaining
graph?

I realize that that's probably naive, but at least it's efficient :-).

Seth		sethb@fid.morgan.com