Search results for: DRZEWA SPINAJĄCE

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

  Publication

  • D. Dereniowski

  - Year 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.

• Graph decomposition for improving memoryless periodic exploration

  Publication

  • A. Kosowski
  • A. Navarra

  - Year 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.

  Full text to download in external service

• Exploiting multi-interface networks: Connectivity and Cheapest Paths

  Publication

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

  - WIRELESS NETWORKS - Year 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...

  Full text to download in external service