Počet záznamů: 1
Online control message aggregation in chain networks
- 1.
SYSNO ASEP 0424763 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Online control message aggregation in chain networks Tvůrce(i) Bienkowski, M. (PL)
Byrka, J. (PL)
Chrobak, M. (US)
Jeż, Ł. (PL)
Sgall, Jiří (MU-W) RID, ORCID, SAI
Stachowiak, G. (PL)Zdroj.dok. Algorithms and Data Structures. - Berlin : Springer, 2013 / Dehne F. ; Solis-Oba R. ; Sack J.-R. - ISSN 0302-9743 - ISBN 978-3-642-40103-9 Rozsah stran s. 133-145 Poč.str. 13 s. Forma vydání Tištěná - P Akce International Symposium, WADS 2013, /13./ Datum konání 12.08.2013-14.08.2013 Místo konání London Země CA - Kanada Typ akce WRD Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova chain networks ; control messages ; control packets Vědní obor RIV BA - Obecná matematika CEP IAA100190902 GA AV ČR - Akademie věd GBP202/12/G061 GA ČR - Grantová agentura ČR EID SCOPUS 84881179034 DOI 10.1007/978-3-642-40104-6_12 Anotace In the Control Message Aggregation (CMA) problem, control packets are generated over time at the nodes of a tree T and need to be transmitted to the root of T. To optimize the overall cost, these transmissions can be delayed and different packets can be aggregated, that is a single transmission can include all packets from a subtree rooted at the root of T. The cost of this transmission is then equal to the total edge length of this subtree, independently of the number of packets that are sent. A sequence of transmissions that transmits all packets is called a schedule. The objective is to compute a schedule with minimum cost, where the cost of a schedule is the sum of all the transmission costs and delay costs of all packets. The problem is known to be NP -hard, even for trees of depth 2. In the online scenario, it is an open problem whether a constant-competitive algorithm exists. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2014
Počet záznamů: 1