Staff View
Frugal Methods for the Independent Set and Graph Coloring Problems.

Descriptive

Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
Genre (authority = RULIB-FS)
Other
Genre (authority = marcgt)
technical report
PhysicalDescription
InternetMediaType
application/pdf
Extent
93 p.
Note (type = special display note)
Technical report DCS-TR-282
Name (authority = RutgersOrg-School); (type = corporate)
NamePart
School of Arts and Sciences (SAS) (New Brunswick)
Name (authority = RutgersOrg-Department); (type = corporate)
NamePart
Computer Science (New Brunswick)
TypeOfResource
Text
TitleInfo
Title
Frugal Methods for the Independent Set and Graph Coloring Problems.
Abstract (type = abstract)
We consider two classical hard graph problems: finding the maximum independent set of vertices, and coloring the vertices with fewest colors possible. We are interested in frugal algorithms for these problems, ones that use limited amount of computing capabilities. Such algorithms yield approximate, rather than exact, solutions, and are valued according to their performance guarantee, which is the maximum factor that approximate solutions can differ from optimal ones. We are primarily interested in two classes of frugal algorithms: polynomial-time, and on-line algorithms. We present several polynomial-time algorithms for obtaining large approximations in graphs containing large independent sets, and use them to improve the best performance guarantees known for both problems. We show how nearly all effective algorithms for these problems fall into yet another category of frugal algorithms, based on removing subgraphs, and obtain tight lower bounds on their performance. For on-line graph coloring, we give strong lower bounds for both deterministic and randomized algorithms, that hold even if the models are weakened in several ways, and improve the best performance guarantee known for randomized on-line coloring. Finally, we prove simple tight bounds on two interpretations of the on-line independent set problem and some of its variations.
Name (type = personal)
NamePart (type = family)
Halldorsson
NamePart (type = given)
Magnus M.
Affiliation
Computer Science (New Brunswick)
Role
RoleTerm (authority = marcrt); (type = text)
author
OriginInfo
DateCreated (encoding = w3cdtf); (keyDate = yes); (qualifier = exact)
1991-10
RelatedItem (type = host)
TitleInfo
Title
Computer Science (New Brunswick)
Identifier (type = local)
rucore21032500001
Location
PhysicalLocation (authority = marcorg); (displayLabel = Rutgers, The State University of New Jersey)
NjNbRU
Identifier (type = doi)
doi:10.7282/T3NK3JMP
Genre (authority = ExL-Esploro)
Technical Documentation
Back to the top

Rights

RightsDeclaration (AUTHORITY = rightsstatements.org); (TYPE = IN COPYRIGHT); (ID = http://rightsstatements.org/vocab/InC/1.0/)
This Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).
Copyright
Status
Copyright protected
Availability
Status
Open
Reason
Permission or license
Back to the top

Technical

RULTechMD (ID = TECHNICAL1)
ContentModel
Document
CreatingApplication
Version
1.4
ApplicationName
GPL Ghostscript 9.07
DateCreated (point = start); (encoding = w3cdtf); (qualifier = exact)
2018-06-06T12:26:23
DateCreated (point = start); (encoding = w3cdtf); (qualifier = exact)
2018-06-06T12:26:23
Back to the top
Version 8.3.13
Rutgers University Libraries - Copyright ©2020