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
<?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>