This HTML5 document contains 38 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
n16http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n14https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
n6https://link.springer.com/book/10.1007/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n13http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n15http://rhydlewis.eu/gcol/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:DSatur
dbo:wikiPageWikiLink
dbr:Recursive_largest_first_algorithm
Subject Item
dbr:Graph_coloring
dbo:wikiPageWikiLink
dbr:Recursive_largest_first_algorithm
Subject Item
dbr:Recursive_largest_first_algorithm
rdfs:label
Recursive largest first algorithm
rdfs:comment
The Recursive Largest First (RLF) algorithm is a heuristic for the NP-hard graph coloring problem. It was originally proposed by Frank Leighton in 1979. The RLF algorithm assigns colors to a graph’s vertices by constructing each color class one at a time. It does this by identifying a maximal independent set of vertices in the graph, assigning these to the same color, and then removing these vertices from the graph. These actions are repeated on the remaining subgraph until no vertices remain.
foaf:depiction
n13:Circle_graph.svg
dcterms:subject
dbc:Graph_algorithms dbc:Graph_coloring dbc:1979_in_computing
dbo:wikiPageID
69680802
dbo:wikiPageRevisionID
1065832821
dbo:wikiPageWikiLink
dbc:Graph_algorithms dbr:Big_O_notation dbr:Bipartite_graph dbr:Chromatic_number dbr:DSatur dbr:Heuristic dbr:Random_graph dbr:Cycle_graph dbr:Wheel_graph dbr:NP-hard n16:Circle_graph.svg dbr:Graph_coloring_problem dbc:Graph_coloring dbr:Maximal_independent_set dbr:Greedy_coloring dbc:1979_in_computing
dbo:wikiPageExternalLink
n6:978-3-030-81054-2 n15:
owl:sameAs
wikidata:Q110443043 n14:GEGKT
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Reflist
dbo:thumbnail
n13:Circle_graph.svg?width=300
dbo:abstract
The Recursive Largest First (RLF) algorithm is a heuristic for the NP-hard graph coloring problem. It was originally proposed by Frank Leighton in 1979. The RLF algorithm assigns colors to a graph’s vertices by constructing each color class one at a time. It does this by identifying a maximal independent set of vertices in the graph, assigning these to the same color, and then removing these vertices from the graph. These actions are repeated on the remaining subgraph until no vertices remain. To form high-quality solutions (solutions using few colors), the RLF algorithm uses specialized heuristic rules to try to identify "good quality" independent sets. These heuristics make the RLF algorithm exact for bipartite, cycle, and wheel graphs. In general, however, the algorithm is approximate and may well return solutions that use more colors than the graph’s chromatic number.
prov:wasDerivedFrom
wikipedia-en:Recursive_largest_first_algorithm?oldid=1065832821&ns=0
dbo:wikiPageLength
5416
foaf:isPrimaryTopicOf
wikipedia-en:Recursive_largest_first_algorithm
Subject Item
wikipedia-en:Recursive_largest_first_algorithm
foaf:primaryTopic
dbr:Recursive_largest_first_algorithm