Wyniki wyszukiwania dla: DRZEWA SPINAJĄCE

• Analiza przybliżonego algorytmu dla problemu szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym.

  Publikacja

  • D. Dereniowski

  - Rok 2004

  W pracy rozważamy kombinatoryczny problem MERST polegający na szukaniu, dla danego grafu, drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym. Dla ogólnych grafów problem MERST jest NP-trudny. W pracy zaproponowano nową funkcję dobroci dla pewnego przybliżonego algorytmu rozwiązującego powyższy problem i przeprowadzono doświadczenia komputerowe w celu porównania nowej z wcześniej znaną funkcją dobroci.

• Exploiting multi-interface networks: Connectivity and Cheapest Paths

  Publikacja

  • A. Kosowski
  • A. Navarra
  • C. Pinotti

  - WIRELESS NETWORKS - Rok 2010

  Let G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at...

  Pełny tekst do pobrania w serwisie zewnętrznym

• Graph decomposition for improving memoryless periodic exploration

  Publikacja

  • A. Kosowski
  • A. Navarra

  - Rok 2009

  W ostatnich latach często badanym problem jest eksploracja anonimowych grafów z lokalnymi etykietami portów przy każdym wierzchołku. Niedawno pokazano [Czyzowicz et al., Proc. SIROCCO'09], że dla każdego grafu istnieje poetykietowanie prowadzące do eksploracji przez automat bezpamięciowy z okresem co najwyżej 13n/3. W niniejszej pracy poprawiamy to ograniczenie do 4n-2, stosując całkowicie nową technikę dekompozycji grafu.

  Pełny tekst do pobrania w serwisie zewnętrznym