Re: help: approximation algorithms for graph separation

Article View: sci.op-research

Article #2

From: Eckhard Hennig
Date: Mon, 15 Mar 1999 00:00

37 lines
2428 bytes

>Hi everyone,
>
>I'd greatly appreciate any pointers to approximation algorithms for the
>following NP-complete problem:
>
>Given an unweighted, undirected graph G, find a small set of _nodes_
>such that removing these nodes disconnects the graph into several
>components of roughly equal size.
>
>Most algorithms I've seen for disconnecting a graph into balanced chunks
>work by removing edges, not nodes.
[...snip...]

You will find such an algorithm in this paper by Sangiovanni-Vincentelli et
al.

A. Sangiovanni-Vincentelli, L. K. Chen, L. O. Chua, "An Efficient Heuristic
Cluster Algorithm for Tearing Large-Scale Networks", IEEE Trans. Circuits
and Systems, vol. CAS-24, pp. 709-717, Dec. 1977

BTW, if there are more recent publications on this issue I'd like to hear
about them, too.

Best regards,

  Eckhard

-----------------------------------------------------------
Dipl.-Ing. Eckhard Hennig      mailto:hennig@itwm.uni-kl.de
Institut fuer Techno- und Wirtschaftsmathematik e.V. (ITWM)
Erwin-Schroedinger-Strasse,  67663 Kaiserslautern,  Germany
  Voice: +49-(0)631-205-3126    Fax: +49-(0)631-205-4139
    http://www.itwm.uni-kl.de/as/employees/hennig.html

     ITWM - Makers of Analog Insydes for Mathematica
        http://www.itwm.uni-kl.de/as/products/ai
-----------------------------------------------------------

Technical Details

Message-ID: <7ciihj$j03$1@sun.rhrk.uni-kl.de>

Path: arc1-ca.pugleaf.net!unknown!not-for-mail

References: <oa53e3732lg.fsf@radiance.lcs.mit.edu+>

Show Full Headers

Complete Article Headers

X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: fd9bd,fb2d6f50a91e7f21
X-Google-Attributes: gidfd9bd,public
X-Google-Thread: 109d8a,fb2d6f50a91e7f21
X-Google-Attributes: gid109d8a,public
X-Google-Thread: 10a1dc,fb2d6f50a91e7f21
X-Google-Attributes: gid10a1dc,public
X-Google-Thread: 10c033,fb2d6f50a91e7f21
X-Google-Attributes: gid10c033,public
X-Google-Thread: f8362,fb2d6f50a91e7f21
X-Google-Attributes: gidf8362,public
X-Google-Thread: 10cc56,fb2d6f50a91e7f21
X-Google-Attributes: gid10cc56,public
From: "Eckhard Hennig" <hennig@itwm.uni-kl.de>
Subject: Re: help: approximation algorithms for graph separation
Date: 1999/03/15
Message-ID: <7ciihj$j03$1@sun.rhrk.uni-kl.de>
X-Deja-AN: 455148657
Content-Transfer-Encoding: 7bit
References: <oa53e3732lg.fsf@radiance.lcs.mit.edu+>
Content-Type: text/plain; charset="iso-8859-1"
X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3
Organization: ITWM
Mime-Version: 1.0
Newsgroups: sci.op-research,sci.math,sci.math.symbolic,sci.logic,comp.theory,aus.computers.logic-prog

Reply to Parent Message