Modele umieszczania grafów w grafach i ich zastosowania

• Autorzy: Bruniecki K.

Warianty tytułu

EN

Models of embedding graphs into graphs with applications

• Języki publikacji: PL

Abstrakty

PL

Celem umieszczania grafu w grafie jest konstrukcja odwzorowania pomiędzy dwoma grafami. Omówione zostały sposoby mierzenia jakości danego odwzorowania. Skrótowo omówione zostały dotychczasowe wyniki teoretyczne obejmujące, przede wszystkim, hiperkostki, drzewa, kraty oraz cykle. Przedstawiona została metodologia postępowania przy konstrukcji i dowodzeniu takich wyników. Wprowadzono nowy model ważony oraz miary jakości umieszczeń dla takiego przypadku. Postawiony został problem umieszczania obciążonych krawędziowo gwiazd i optymalny algorytm jest przedstawiony. Ponadto omówione zostały zastosowania przedstawionych modeli, będące najistotniejszą motywacją dla wysiłków podejmowanych w tym temacie.

EN

The aim of embedding graph into graph is to construct a function that maps one host graph into another guest graph. There are presented measures which may be used to evaluate such a mapping. The introduction to current theoretical results is given. Such results focus on hypercubes, trees, meshes and cycles. Main methods of constructing and proving such results are considered. New weighted model and quality measures of embedding in such a model are introduced. Problem of embedding weighted stars is stated and optimal algorithm is presented. Additionally, applications of presented models are discussed, since they give important motivation to efforts in this subject.

Słowa kluczowe

PL

grafy; model "jeden do jednego"; model ważony; hiperkostki

EN

graphs; model graphs into graphs; weighted model; hypercubes

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2007
• Tom: T. 13
• Strony: 457--464
• Opis fizyczny: Bibliogr. 13 poz, rys.

Twórcy

autor

Bruniecki K.

• Katedra Algorytmów i Modelowania Systemów, Politechnika Gdańska

Bibliografia

• [1] Bein W. W., Lannore L L, Shields C., Sudborough I. H.: Embedding a complete binary tree into a three-dimensional grid. Journal of Interconnection Networks, s.III-130, nr 5(2), 2004.
• [2] Monien B., Sudborough I. H.: Embedding one interconnection network in another. Computing Supplementum, s.257-282, nr 7, 1990.
• [3] Raspaud A., Sykora O., Vrto 1.: Congestion and dilation, similarities and differences: A survey. In SIROCCO, s.269-280, 2000.
• [4] Garey M., Johnson D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.
• [5] Woźniak M.: Wprowadzenie do problemów komunikacji w grafach. Wydawnictwa AGH, 1999.
• [6] Rosenberg A., Snyder L: Bounds on the cost of data encodings. Mathematical System Theory, s.9-39, nr 12, 1978.
• [7] Papadimitriou C. H.: The NP-completeness of the bandwidth minimization problem. Computing, s.263-270, nr 16, 1976.
• [8] Blache G., Karpinski M., Wirtgen J.: On approximation intractability of the bandwidth problem. Electronic Colloquium on Computational Complexity (ECCC), s., nr 5(14),1998.
• [9] Chavez J. D., Trapp R.: The cyclic cutwidth of trees. Discrete Applied Mathematics, s.25-32, nr 87, 1998.
• [10] Hromkovic J., Müller V., Sykora O., Vrto I.: On embeddings in cycles. Information and Computation, s.302-305, nr 118(2), 1995.
• [11] Wagner A., Corneil D.: Embedding tree in a hypercube is NP-complete. SIAM Journal on Computing, s.570-590, nr 19, 1990.
• [12] Newsome J., Song D.: GEM: Graph EMbedding for routing and data-centric storage in sensor networks without geographic information. W: SenSys '03, Proceedings of the 1st international conference on Embedded networked sensor systems, s.76-88, ACM Press 2003.
• [13] Röttger M., Schroeder U.-P., Simon J.: Virtual topology library for PARIX Technical report, University of Paderborn, 1994.