Lovasz theta-function of a class of graphs representing digital lines

ResearchSpace/Manakin Repository

Show simple item record

dc.contributor.author Brimkov, Valentin en
dc.contributor.author Barneva, Reneta en
dc.date.accessioned 2008-08-21T01:57:28Z en
dc.date.available 2008-08-21T01:57:28Z en
dc.date.issued 2004 en
dc.identifier.citation Communication and Information Technology Research Technical Report 138, (2004) en
dc.identifier.issn 1178-3607 en
dc.identifier.uri http://hdl.handle.net/2292/2828 en
dc.description You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). en
dc.description.abstract We consider the problem of estimating the Shannon capacity of a circulant graph C_nj of degree four with n vertices and chord length j, , by computing its Lovasz theta function theta(C_nj ). Our interest in this problem is driven by possible applications to error-free communication of data describing the structure of a digital line. The latter can be represented in terms of spyrographs [12], which, as a matter of fact, are circulants of degree four. We present an algorithm for theta(C_nj ) computation that takes O(j) operations if j is an odd number, and O(n/j) operations if j is even. On the considered class of graphs our algorithm strongly outperforms the known algorithms for theta function computation. en
dc.publisher CITR, The University of Auckland, New Zealand en
dc.relation.ispartofseries Communication and Information Technology Research (CITR) Technical Report Series en
dc.rights Copyright CITR, The University of Auckland. You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site under terms that include this permission. All other rights are reserved by the author(s). en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.source.uri http://citr.auckland.ac.nz/techreports/2004/CITR-TR-138.pdf en
dc.title Lovasz theta-function of a class of graphs representing digital lines en
dc.type Technical Report en
dc.subject.marsden Fields of Research::280000 Information, Computing and Communication Sciences en


Full text options

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Advanced Search

Browse