Linear kernels in linear time, or how to save k colours in O(n2) steps | NOVA. The University of Newcastle's Digital Repository

Home

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/32899

Title: Linear kernels in linear time, or how to save k colours in O(n2) steps
Author/Creator: Fellows, Mike; Juedes, David; Chor, Benny
Description: This paper examines a parameterized problem that we refer to as n - k GRAPH COLORING, i.e., the problem of determining whether a graph G with n vertices can be colored using n - k colors.
Relation: 30th International Workshop, WG 2004. Graph-theoretic concepts in computer science : 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004 : revised papers (Bad Honnef, Germany June 21-23, 2004) p. 257-269
Date: 2004
Publisher: Springer
Keyword(s): graph theory; graph covering; kernel method; graph colouring; linear time
Resource Type: conference paper
Identifier: http://hdl.handle.net/1959.13/32899
Identifier: ISBN:3540241329

15 Visitors

19 Hits

NOVA. The University of Newcastle's Digital Repository