Automatically assigned DDC number: 5115

Manually assigned DDC number: 5115

Title: Journal of Graph Algorithms and Applications

Author:

Subject: Hoong Chuin Lau Journal of Graph Algorithms and Applications

Description: We present practical algorithms for constructing partitions of graphs into a fixed number of vertex-disjoint subgraphs that satisfy particular degree constraints. We use this in particular to find k-cuts of graphs of maximum degree Delta that cut at least a kGamma1 k (1 + 1 2Delta+kGamma1 ) fraction of the edges, improving previous bounds known. The partitions also apply to constraint networks, for which we give a tight analysis of natural local search heuristics for the maximum constraint satisfaction problem. These partitions also imply efficient approximations for several problems on weighted bounded-degree graphs. In particular, we improve the best performance ratio for the weighted independent set problem to 3 Delta+2 , and obtain an efficient algorithm for coloring 3-colorable graphs with at most 3Delta+2 4 colors. Communicated by M. Furer: submitted February 1996; revised March 1997. Halld'orsson, Lau, Low-degree Graph Partitioning , JGAA, 1(3) 1--13 (1997) 2 1 Intro...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1997-12-05

Pubyear: unknown

Format: ps

Identifier: http://citeseer.ist.psu.edu/140202.html

Source: http://webdoc.gwdg.de/edoc/e/EMIS/journals/JGAA/accepted/97/HalldorssonLau97.1.3.ps.gz

Language: en

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Journal   of   Graph   Algorithms   and   Applications">

            <identifier   Org="ISBN:0471731900"   Paper_ID="SELF"   Extracted="0471731900"   DDC="005.74"   Normalized_DDC="00574"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0821828150"   Paper_ID="SELF"   Extracted="0821828150"   DDC="511/.5"   Normalized_DDC="5115"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0898713552"   Paper_ID="SELF"   Extracted="0898713552"   DDC="519.4/0285/51"   Normalized_DDC="5194028551"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540001581"   Paper_ID="SELF"   Extracted="3540001581"   DDC="511/.5"   Normalized_DDC="5115"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540212582"   Paper_ID="SELF"   Extracted="3540212582"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540245286"   Paper_ID="SELF"   Extracted="3540245286"   DDC="511.5"   Normalized_DDC="5115"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:354024574X"   Paper_ID="SELF"   Extracted="354024574X"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540314253"   Paper_ID="SELF"   Extracted="3540314253"   DDC="511/.5"   Normalized_DDC="5115"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540322124"   Paper_ID="SELF"   Extracted="3540322124"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540405453"   Paper_ID="SELF"   Extracted="3540405453"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540433090"   Paper_ID="SELF"   Extracted="3540433090"   DDC="511/.5"   Normalized_DDC="5115"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540709037"   Paper_ID="SELF"   Extracted="3540709037"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540771182"   Paper_ID="SELF"   Extracted="3540771182"   />

            <identifier   Org="ISBN:3540775366"   Paper_ID="SELF"   Extracted="3540775366"   DDC="511/.5"   Normalized_DDC="5115"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:354077890X"   Paper_ID="SELF"   Extracted="354077890X"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:9812388559"   Paper_ID="SELF"   Extracted="9812388559"   />

            <identifier   Org="ISBN:9812389393"   Paper_ID="SELF"   Extracted="9812389393"   />

      </rec>

</references_metadata>

www.000webhost.com