Abstract-Designing ett overlay nätverk för att publicera / prenumerera kommunikation i ett system där noder kan prenumerera på många olika ämnen av intresse är av grundläggande betydelse. För skalbarhet och effektivitet är det viktigt att hålla graden av noderna i publicerings-/prenumerationssystemet låg. Det är bara naturligt då att formalisera följande problem: Med tanke på en samling av noder och deras ämne prenumerationer, ansluta noderna till en graf som har minst möjliga maximal grad på ett sådant sätt att för varje ämne, grafen induceras av noderna intresserade är ansluten. Vi presenterar den första polynom-tid logaritmisk approximation algoritm för detta problem och bevisa en nästan tight lägre gräns på approximation förhållandet. Våra experimentella resultat visar att vår algoritm drastiskt förbättrar den maximala graden av publicering/prenumeration overlay-system. Vi föreslår också en variation av problemet genom att se till att varje ämnesanslutet overlay-nät har konstant diameter samtidigt som den genomsnittliga graden hålls låg. Vi presenterar tre heuristik för detta problem som garanterar att varje ämne ansluten overlay nätverk kommer att vara av diameter 2 och som syftar till att hålla den totala genomsnittliga nodgrad låg. Våra experimentella resultat validerar våra algoritmer, vilket visar att våra algoritmer kan uppnå mycket låg diameter utan att öka genomsnittsgraden med mycket.
Onus och Richa REF analyserade MinMax-TCO-problemet med att minimera den maximala graden av ett ämnesanslutet overlay-nätverk.
Minimum Maximum-Degree Publish–Subscribe Overlay Network Design
{'venue': 'IEEE/ACM Transactions on Networking', 'journal': 'IEEE/ACM Transactions on Networking', 'mag_field_of_study': ['Computer Science']}