Wyniki wyszukiwania - BazTech

1

Constructing Node-Independent Spanning Trees in Augmented Cubes

Cheng Baolei, Fan Jianxi, Lyu Qiang, Lin Cheng-Kuan, Li Xiaoyan, Chen Guo

Fundamenta Informaticae

|

2020

|

Vol. 176, nr 2

103--128

EN

For a network, edge/node-independent spanning trees (ISTs) can not only tolerate faulty edges/nodes, but also be used to distribute secure messages. As important node-symmetric variants of the hypercubes, the augmented cubes have received much attention from researchers. The n-dimensional augmented cube AQn is both (2n ‒ 1)-edge-connected and (2n ‒ 1)-nodeconnected (n≠3), thus the well-known edge conjecture and node conjecture of ISTs are both interesting questions in AQn. So far, the edge conjecture on augmented cubes was proved to be true. However, the node conjecture on AQn is still open. In this paper, we further study the construction principle of the node-ISTs by using the double neighbors of every node in the higher dimension. We prove the existence of 2k − 1 node-ISTs rooted at node 0 in AQn ( 00...0 n – k ) ( n ≥ k ≥ 4 ) by proposing an ingenious way of construction and propose a corresponding O (N logN ) time algorithm, where N = 2k is the number of nodes in AQn ( 00...0 n – k ) .

2

Algorytmy heurystyczne w trójwymiarowym zagadnieniu pakowania

Chmiel W., Kadłuczka P., Wala K., Jędrusik S.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2010

|

T. 14, z. 3/2

827-840

PL

W artykule zaprezentowano zagadnienie trójwymiarowego pakowania kontenera paczkami o regularnych wymiarach, ze współczynnikiem wypełnienia kontenera jako kryterium oceny. Przebadano zarówno procedury konstrukcyjne, jak i algorytm popraw bazujący na algorytmie symulowanego wyżarzania. Stosowane w algorytmach rozwiązanie problemu pakowania jest reprezentowane w postaci czterech sekwencji liczb. W przedstawionych wynikach eksperymentów wykorzystano instancje testowe zawierające do 400 paczek.

EN

In this paper we examine the problem of optimal packing of a three-dimensional container with rectangular boxes such that the volume of the packed boxes is maximized. We investigate fast constructive procedures and an approximation algorithm based on simulated annealing. In all developed algorithms solutions are represented in a form of four sequences. Extensive computational results involving various test instances up to 400 boxes, are presented.

3

Problem gniazdowy z ograniczeniem bez czekania. Równoległe algorytmy tabu

Makuchowski M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2008

|

z. 150

175-181

PL

W pracy opisane są równoległe algorytmy poszukiwania z zabronieniami, dedykowane gniazdowemu problemowi z ograniczeniem bez czekania. Proponowane algorytmy zbudowane są z nadrzędnego algorytmu bazującego na wspomnianej technice oraz sterowanego algorytmu konstrukcyjnego. Poszukiwania ograniczone są tylko do rozwiązań możliwych do wygenerowania przez wspomniany algorytm konstrukcyjny. W pracy przedstawia się analizę porównawczą zaproponowanych algorytmów.

EN

This paper deals with parallel tabu search algorithms for a job shop problem with a no-wait constraint and a makespan criterion. The proposed algorithms consist of a master algorithm based on the mentioned technique and slave constructive algorithm. This approach reduces the number of solutions to check only to solutions that can be generated by means of the constructive algorithm. In this paper a comparative analysis of the proposed algorithms is presented.