Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the list coloring of k-band buffering cellular graphs
KTH, School of Electrical Engineering and Computer Science (EECS).
2018 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The optimal channel allocation problem in cellular networks is often formulated in a graph theoretic framework. One of its variants–where each access point knows the list of its free channels–is related the so-called list coloring problem and is closely related to the channel allocation of IEEE 802.11 systems. In spite of the fact that the list coloring problem is NP-complete for arbitrary graphs, we show that there exists a polynomial time algorithm that k-list colors an arbitrary graph where k is the Szekeres–Wilf number of the graph. In addition, an upper bound for the choice number of k-band buffering cellular graphs is obtained proving that they are (3k(k + 1)/2 + 1)-choosable.

A Java application is implemented to compute the Szekeres–Wilf number of generated cellular graph in order to facilitate making further conjectures of sharper upper bounds for the choice number.

Abstract [sv]

Det optimala kanalallokeringsproblemet i mobilnät formuleras ofta i en grafteoretisk ram. En av dess varianter, där varje accesspunkt känner till listan av fria kanaler–är relaterad till det så kallade listfärgningsproblemet och är nära besläktat med kanaltilldelningen i IEEE 802.11-system. Trots det faktum att listfärgningsproblemet är NP-komplett för godtyckliga grafer, visar vi att det finns en algoritm med en komplexitet i polynom tid som k-lista färgar en godtycklig graf där k är Szekeres-Wilf-numret av grafen. Dessutom erhålls en övre gräns (3k(k +1)/2+1), för valet av antal k-band buffrande cellulära grafer.En Java-applikation är implementerad för att beräkna Szekeres–Wilf-numret av genererade cellulär graf för att underlätta fortsatt arbete med att ytterligare finna skarpare övre gränser för valnumret.

Place, publisher, year, edition, pages
2018. , p. 33
Series
TRITA-EECS-EX ; 20108
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-254888OAI: oai:DiVA.org:kth-254888DiVA, id: diva2:1335852
Subject / course
Electrical Engineering
Educational program
Degree of Master
Supervisors
Examiners
Available from: 2019-07-08 Created: 2019-07-08 Last updated: 2019-07-08Bibliographically approved

Open Access in DiVA

fulltext(1162 kB)9 downloads
File information
File name FULLTEXT01.pdfFile size 1162 kBChecksum SHA-512
107e1b73c44635c87f870cc327fc950bcbb86a217b1ab788664469529b3a836341a4189523b675cea0db7cd610f313f39441727e111a5211d71e6a05dd96c963
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 9 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 51 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf