X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f
X-Recipient: geda-user AT delorie DOT com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20120113;
        h=mime-version:in-reply-to:references:date:message-id:subject:from:to
         :content-type;
        bh=mfMDQuwXTR43yDt8Baq8P4Bk1c3pIrtbfIK3ZvXDEmc=;
        b=uZ2iqc0fINJw+Xis42xW2Sas2s0TFe90aykttbGlp9J+KhKrvcffOAa8jtdqCx103e
         eLLpfCFDSrCNCo94Us6WvNb3tfrEPHZiVlqMuf+dXgE1zcQyKFlUmFs+zmykoj+L4+tI
         AO/OQcqHp6Se/hppNTfdjNV2O7QztHjEh8t3SO9xhk4zfvusU7tZO80nx6kNzQNsnFdX
         J6aPhQ/Skgj0+03gHfAMCZpeya00T5O2PvY/6VCSnxa4fXyELTlRgpWLHL86NJfZ00JJ
         nJNVEK5f/udOxB5gmukvYCSdPfOGUDUXOBtFDhmVwQSBeBozTmwR9m3PLbw/Xq4NLs7q
         Fgag==
MIME-Version: 1.0
In-Reply-To: <alpine.DEB.2.00.1212111935190.26605@igor2priv>
References: <20121204183305 DOT 6b04c0dc AT jive DOT levalinux DOT org>
	<20121208112649 DOT 388a9d22 AT jive DOT levalinux DOT org>
	<1355011808 DOT 19390 DOT 8 DOT camel AT localhost>
	<alpine DOT DEB DOT 2 DOT 00 DOT 1212090407031 DOT 26605 AT igor2priv>
	<1355188647 DOT 12937 DOT 14 DOT camel AT localhost>
	<alpine DOT DEB DOT 2 DOT 00 DOT 1212110530020 DOT 26605 AT igor2priv>
	<alpine DOT DEB DOT 2 DOT 00 DOT 1212111935190 DOT 26605 AT igor2priv>
Date: Tue, 11 Dec 2012 13:18:46 -0900
Message-ID: <CAC4O8c__Yhb8ZijkVeZzELtNMAO8-=V3aDiEdiCC=BPMPy67Xw@mail.gmail.com>
Subject: Re: [geda-user] Find rat lines
From: Britton Kerin <britton DOT kerin AT gmail DOT com>
To: geda-user AT delorie DOT com
Content-Type: text/plain; charset=ISO-8859-1
Reply-To: geda-user AT delorie DOT com
Errors-To: nobody AT delorie DOT com
X-Mailing-List: geda-user AT delorie DOT com
X-Unsubscribes-To: listserv AT delorie DOT com
Precedence: bulk

On Tue, Dec 11, 2012 at 9:59 AM,  <gedau AT igor2 DOT repo DOT hu> wrote:
>
>
> On Tue, 11 Dec 2012, gedau AT igor2 DOT repo DOT hu wrote:
>
>> I can ask a friend today who is good in graph theory.
>
>
> Today we sat together and I demonstrated the problem in PCB and described
> the details. After modelling the problem (graphs) he evaluated both
> solutions (propagation nets and finding cutting edges).
>
> After decomposing the problem, he concluded that finding the cutting edges
> may be an NP problem (in case it is important to minimize the number of
> cuts) and would be impossible to solve on a large board with a complicated
> situation (multiple traces causing shorts).

Perhaps I don't understand what's being done, but there are some faster
minimum-cut algorithms:

   http://en.wikipedia.org/wiki/Minimum_cut
   http://en.wikipedia.org/wiki/Karger%27s_algorithm

It seems like the difficulty would be keeping the graph up-to-date across
all existing PCB operations (part move, past, manual wire, etc.)

Britton