Maximum size of the pareto cost sets for multi-constrained optimal routing

Basit Öğe Kaydı
dc.contributor.authorKaplan, Derya Yıltaş
dc.date.accessioned2022-01-28T09:43:30Z
dc.date.available2022-01-28T09:43:30Z
dc.date.issued2017
dc.description.abstractAbstract: Routing under multiple independent constrains in point-to-point networks has been studied for over 10 years. Its NP-hardness keeps pushing researchers to study approximate algorithms and heuristics, and many results have been published in these years. To the best of our knowledge, the nature of its average case has been explored only for the selfadaptive multiple constraints routing algorithm (SAMCRA), which is an algorithm about multiple constraints routing. In this paper, we simplify SAMCRA into a format that is convenient for our average case analysis. This variant algorithm gives optimal solutions also for very large dimensional networks such as with more than 1000 nodes. Although it runs in exponential time in the worst case, we prove that its average case time complexity is bounded by a polynomial function of the number of nodes in the network. Lastly, we give empirical results that align with our theoretical work.en_US
dc.fullTextLevelFull Texten_US
dc.identifier.issn1300-0632
dc.identifier.issn1300-0632
dc.identifier.urihttps://hdl.handle.net/11411/4414
dc.indekslendigikaynakTR-Dizinen_US
dc.issue2en_US
dc.language.isoenen_US
dc.nationalInternationalen_US
dc.numberofauthors1en_US
dc.pages1211 - 1222en_US
dc.publisherTurkish Journal of Electrical Engineering and Computer Sciencesen_US
dc.relation.ispartofTurkish Journal of Electrical Engineering and Computer Sciencesen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectAlgorithmen_US
dc.subjectcomputer networken_US
dc.subjectexpected polynomial timeen_US
dc.subjectmulti-constrained routingen_US
dc.subjectpareto frontieren_US
dc.subjectpareto optimisationen_US
dc.subjectquality of serviceen_US
dc.subjectrouting algorithmen_US
dc.titleMaximum size of the pareto cost sets for multi-constrained optimal routing
dc.typeArticle
dc.volume25en_US

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim
İsim:
2017Kaplan.pdf
Boyut:
400.62 KB
Biçim:
Adobe Portable Document Format
Açıklama:
İndir
Lisans paketi
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
license.txt
Boyut:
1.71 KB
Biçim:
Item-specific license agreed upon to submission
Açıklama:
İndir

Koleksiyon

Faculty of Engineering and Natural Sciences
TR Dizin Indexed Publications