Graph Imperfection II.
The imperfection ratio is a graph invariant which indicates how good a lower bound the weighted clique number gives on the weighted chromatic number, in the limit as weights get large. Its introduction was motivated by investigations of the radio channel assignment problem, where one has to assign c...
| Asıl Yazarlar: | , |
|---|---|
| Materyal Türü: | Journal article |
| Dil: | English |
| Baskı/Yayın Bilgisi: |
Elsevier
2001
|
| _version_ | 1826296703172476928 |
|---|---|
| author | Gerke, S McDiarmid, C |
| author_facet | Gerke, S McDiarmid, C |
| author_sort | Gerke, S |
| collection | OXFORD |
| description | The imperfection ratio is a graph invariant which indicates how good a lower bound the weighted clique number gives on the weighted chromatic number, in the limit as weights get large. Its introduction was motivated by investigations of the radio channel assignment problem, where one has to assign channels to transmitters and the demands for channels at some transmitters are large. In this paper we show that the imperfection ratio behaves multiplicatively under taking the lexicographic product, which permits us to identify its possible values, investigate its extremal behaviour and its behaviour on random graphs, explore three upper bounds, and show that it is NP-hard to determine. © 2001 Academic Press. |
| first_indexed | 2024-03-07T04:20:26Z |
| format | Journal article |
| id | oxford-uuid:cad366ad-dda7-435f-91d6-7b6eacced40c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T04:20:26Z |
| publishDate | 2001 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:cad366ad-dda7-435f-91d6-7b6eacced40c2022-03-27T07:10:17ZGraph Imperfection II.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:cad366ad-dda7-435f-91d6-7b6eacced40cEnglishSymplectic Elements at OxfordElsevier2001Gerke, SMcDiarmid, CThe imperfection ratio is a graph invariant which indicates how good a lower bound the weighted clique number gives on the weighted chromatic number, in the limit as weights get large. Its introduction was motivated by investigations of the radio channel assignment problem, where one has to assign channels to transmitters and the demands for channels at some transmitters are large. In this paper we show that the imperfection ratio behaves multiplicatively under taking the lexicographic product, which permits us to identify its possible values, investigate its extremal behaviour and its behaviour on random graphs, explore three upper bounds, and show that it is NP-hard to determine. © 2001 Academic Press. |
| spellingShingle | Gerke, S McDiarmid, C Graph Imperfection II. |
| title | Graph Imperfection II. |
| title_full | Graph Imperfection II. |
| title_fullStr | Graph Imperfection II. |
| title_full_unstemmed | Graph Imperfection II. |
| title_short | Graph Imperfection II. |
| title_sort | graph imperfection ii |
| work_keys_str_mv | AT gerkes graphimperfectionii AT mcdiarmidc graphimperfectionii |