| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 4 / 4
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
2-local 3/4-competitive algorithm for multicoloring hexagonal graphs
Petra Šparl, Janez Žerovnik, 2005, izvirni znanstveni članek

Opis: An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference.A cellular network is generally modeled as a subgraph of the infinite triangular lattice. Frequency assignment problem can be abstracted asa multicoloring problem on a weighted hexagonal graph, where the weights represent the number of calls to be assigned at vertices. In this paper we present a distributed algorithm for multicoloring hexagonal graphs using only the local clique numbers ▫$omega_1(v)$▫ and ▫$omega_2(v)$▫ at each vertex v of the given hexagonal graph, which can be computed from local information available at thevertex. We prove the algorithm uses no more than ▫$4omega(G)/3$▫ colors for any hexagonal graph G, without explicitly computing the global clique number ▫$omega(G)$▫. We also prove that our algorithm is 2-local, i.e., the computation at a vertex v ▫$in$▫ G uses only information about the demands of vertices whose graph distance from v is less than or equal to 2.
Ključne besede: mathematics, graph theory, graph colouring, 2-local distributed algorithm, cellular networks, frequency planning
Objavljeno: 01.06.2012; Ogledov: 1234; Prenosov: 51
URL Povezava na celotno besedilo

2.
An optimal permutation routing algorithm for full-duplex hexagonal mesh networks
Ignasi Sau Walls, Janez Žerovnik, 2006

Opis: In the permutation routing problem, each processor is the origin of at most one packet and each processor is the destination of no more than one packet. We study this problem in an hexagonal network (that is, a finite convex subgraph of a triangular grid), a widely used network in practical applications. We use the addressing scheme described by F.G. Nocetti, I. Stojmenovic and J. Zhang (2002, IEEE Trans. on Parallel and Distrib. Systems). In this paper, a distributed optimal routing algorithm for full-duplex hexagonal mesh networks is presented. Furthermore, we prove that this algorithm is oblivious and translation invariant.
Ključne besede: mathematics, hexagonal networks, permutation routing, shortest path, distributed algorithm, communication networks, oblivious algorithm
Objavljeno: 10.07.2015; Ogledov: 366; Prenosov: 21
URL Povezava na celotno besedilo

3.
2-local distributed algorithms for generalized coloring of hexagonal graphs
Petra Šparl, Janez Žerovnik, 2005, objavljeni znanstveni prispevek na konferenci

Opis: A 2-local distributed approximation algorithm for multicoloring of a triangle-free hexagonal graph which uses at most ▫$lceil frac{5omega(G)}{4} rceil + 3$▫ colors is presented.
Ključne besede: matematika, teorija grafov, barvanje grafov, aproksimacijski algoritem, frekvenčni načrt, ▫$k$▫-lokalen porazdeljen algoritem, mathematics, graph theory, approximation algorithms, graph coloring, frequency planning, ▫$k$▫-local distributed algorithm
Objavljeno: 10.07.2015; Ogledov: 451; Prenosov: 51
URL Povezava na celotno besedilo

4.
An optimal permutation routing algorithm on full-duplex hexagonal networks
Ignasi Sau Walls, Janez Žerovnik, 2008, izvirni znanstveni članek

Opis: In the permutation routing problem, each processor is the origin of at most one packet and the destination of no more than one packet. The goal is to minimize the number of time steps required to route all packets to their respective destinations, under the constraint that each link can be crossed simultaneously by no more than one packet. We study this problem in a hexagonal network, i.e. a finite subgraph of a triangular grid, which is a widely used network in practical applications. We present an optimal distributed permutation routing algorithm for full-duplex hexagonal networks, using the addressing scheme described by Nocetti et al. Furthermore, we prove that this algorithm is oblivious and translation invariant.
Ključne besede: mathematics, hexagonal networks, permutation routing, shortest path, distributed algorithm, communication networks, oblivious algorithm
Objavljeno: 10.07.2015; Ogledov: 396; Prenosov: 53
.pdf Celotno besedilo (535,46 KB)
Gradivo ima več datotek! Več...

Iskanje izvedeno v 0.13 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici