Search results for "Spanning tree"
showing 3 items of 53 documents
A new minimum trees-based approach for shape matching with improved time computing : application to graphical symbols recognition
2010
Recently we have developed a model for shape description and matching. Based on minimum spanning trees construction and specifics stages like the mixture, it seems to have many desirable properties. Recognition invariance in front shift, rotated and noisy shape was checked through median scale tests related to GREC symbol reference database. Even if extracting the topology of a shape by mapping the shortest path connecting all the pixels seems to be powerful, the construction of graph induces an expensive algorithmic cost. In this article we discuss on the ways to reduce time computing. An alternative solution based on image compression concepts is provided and evaluated. The model no longe…
A non-cooperative approach to the folk rule in minimum cost spanning tree problems
2023
This paper deals with the problem of finding a way to distribute the cost of a minimum cost spanning tree problem between the players. A rule that assigns a payoff to each player provides this distribution. An optimistic point of view is considered to devise a cooperative game. Following this optimistic approach, a sequential game provides this construction to define the action sets of the players. The main result states the existence of a unique cost allocation in subgame perfect equilibria. This cost allocation matches the one suggested by the folk rule. The authors thank the support of the Spanish Ministry of Science, Innovation and Universities, the Spanish Ministry of Economy and Compe…
Counting the minimum node weight spanning trees for broadcast transmission in wireless sensor networks
2017
Artykuł przedstawia algorytm optymalizacji zużycia energii dla broadcastu w sieciach sensorowych. Transmisja broadcastu pozwala na wysłanie danych do wszystkich portów składających się na sieć. Bezprzewodowe sieci sensorowe zbudowane są z rozproszonych urządzeń pomiarowych. Mają one ograniczone zasoby energii. W tym artykule stworzymy model sieci sensorowej z jednym sensorem broadcastującym. Do tej sieci użyjemy algorytmu znajdującego minimalne spinające drzewo wag, pozwalające na oszczędne wykorzystanie energii sensorów.