Frequency assignment in mobile and radio networks

dc.contributor.author	Φωτάκης, Δημήτριος	el
dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Πεντάρης, Γιώργος	el
dc.contributor.author	Σπυράκης, Παύλος	el
dc.date.accessioned	2015-05-24T20:47:04Z
dc.date.available	2015-05-24T20:47:04Z
dc.date.issued	2015-05-24
dc.identifier.uri	http://hdl.handle.net/11400/11090
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.2465	en
dc.subject	συχνότητα εκχώρησης
dc.subject	κινητά δίκτυα
dc.subject	ραδιοφωνικά δίκτυα
dc.subject	Frequency Assignment
dc.subject	Mobile networks
dc.subject	Radio Networks
dc.title	Frequency assignment in mobile and radio networks	en
heal.type	journalArticle
heal.classification	Πληροφορική
heal.classification	Μαθηματικά
heal.classification	Computer science
heal.classification	Mathematics
heal.classificationURI	N/A-Πληροφορική
heal.classificationURI	N/A-Μαθηματικά
heal.classificationURI	http://skos.um.es/unescothes/C00750
heal.classificationURI	http://skos.um.es/unescothes/C02437
heal.identifier.secondary	DOI: 10.1.1.26.2465
heal.language	en
heal.access	campus
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1998
heal.bibliographicCitation	Fotakis, D., Pantziou, G., Pentaris, G. and Spirakis, P. (1998) Frequency Assignment in Mobile and Radio Networks. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Special issue on Networks in Distributed Computing. [Online] 45, pp.73-90. Available from: http://citeseerx.ist.psu.edu [Accessed 24/05/2015]	en
heal.abstract	We deal with the problem of frequency assignment in mobile and general radio networks, where the signal interferences are modeled using an interference graph G. Our approach uses graph theoretic and optimization techniques. We rst study on-line algorithms for frequency assignment in mobile networks. We prove that the greedy algorithm is -competitive, where is the maximum degree of G. We next employ the \classify and randomly select" paradigm to give a 5-competitive randomized algorithm for the case of planar interference graphs. We also show how the problem of on-line frequency assignment in mobile networks with multiple available frequency channels reduces to the problem of on-line frequency assignment in mobile networks with a single channel. We continue to study radio coloring and radio labeling as combinatorial models for frequency assignment in general radio networks. In both problems, the ob jective is to minimize the maximum frequency channel used, while the transmitters being adjacent in the interference graph must be assigned channels that di er by at least two from each other. In radio coloring, di erent channels must be assigned to transmitters that are at distance two in the interference graph. Additionally, in radio labeling, all the transmitters must be assigned distinct frequency channels. Radio labelling is shown to be equivalent to a generalization of Hamiltonian path, and both problems remain N P -complete, even if they restricted to graphs of diameter two. We nally present algorithms and lower bounds for two on-line variations of radio labeling.	en
heal.journalName	DIMACS Series in Discrete Mathematics and Theoretical Computer Science	en
heal.journalType	peer-reviewed
heal.fullTextAvailability	true