A method involving constraint programming for generating integral graphs without ± 1 in the spectrum : a case study

• Autorzy: Zwierzyński K. , Meissner A. , Niwińska M.

Warianty tytułu

PL

Zastosowanie programowania z więzami do generowania grafów całkowitych bez ± 1 w spektrum

• Języki publikacji: EN

Abstrakty

EN

We consider a method where the constraint programming over finite domains is used for describing relationships among some properties of graphs. The process of constraint solving results in the set of values, which act as input parameters for the graph generation algorithm. In this way, the space of possibly generated graphs is reduced. We present a case study of the application of this approach to the problem of finding all connected, integral, non-regular and bipartite graphs, with a maximum vertex degree four not containing ± 1 in the spectrum (i.e., SL4-graphs).

PL

W artykule rozważa się wariant metody konstruowania grafów poprzez generowanie a następnie przeszukiwanie klas grafów, do których należą rozpatrywane grafy. Proponuje się przy tym zastosowanie metodyki programowania z więzami (ang. constraint programming over finite domains) do opisywania zależności, jakie zachodzą między niektórymi właściwościami grafów. W ten sposób ogranicza się a zarazem precyzuje zbiór parametrów algorytmu generującego grafy. W konsekwencji, zostaje zredukowana przestrzeń, którą należy przeszukiwać. Praca zawiera analizę przykładu zastosowania tego ujęcia do skonstruowania wszystkich spójnych, nieregularnych, dwudzielnych grafów całkowitych o maksymalnym stopniu wierzchołków równym 4 niezawierających ± 1 w spektrum.

Słowa kluczowe

EN

constraint programming; generating graphs

PL

programowanie z więzami; generowanie grafów

• Wydawca: Poznańskie Towarzystwo Przyjaciół Nauk
• Czasopismo: Studia z Automatyki i Informatyki
• Rocznik: 2010
• Tom: T. 35
• Strony: 105--114
• Opis fizyczny: Bibliogr. 9 poz., rys., tab.

Twórcy

autor

Zwierzyński K.

autor

Meissner A.

autor

Niwińska M.

• Poznan University of Technology, pl. M. Skłodowskiej-Curie 5, 60-965 Poznań, Poland,

Bibliografia

• [1] Apt, K. R., Principles of Constraint Programming, Cambridge Univ. Press, 2003.
• [2] Balińska K. T., Simić S. K., Zwierzyński K. T., Which non-regular bipartite integral graphs with maximum degree four do not have ±1 as eigenvalues?, Discrete Mathematics 286 (1-2): 2004, pp. 15-24.
• [3] Lepović M., Simić S. K., Balińska K.T., Zwierzyński K. T., There are 93 non-regular, bipartite integral graphs with maximum degree four, Computer Science Center Report No 511, The Technical University of Poznań, 2005, pp. 1-17.
• [4] Marciniak A., Gregulec D., Kaczmarek J., Podstawowe procedury numeryczne w języku Turbo Pascal, Wydawnictwo Nakom, Poznań, 1997.
• [5] McKay B. D., Nauty, http://cs.anu.edu.au/bdm/nauty/
• [6] Meissner A., Niwińska M. A., Zwierzyński K. T., Computing the Irregularity Strength of Connected Graphs by Parallel Constraint Solving in the Mozart System, Lecture Notes in Computer Science, Volume 4967, 2008, pp. 1096-1103.
• [7] Simić S. K., Personal communication.
• [8] Smolka G., The Oz Programming Model Computer Science Today, Lecture Notes in Computer Science, Volume 1000, 1995, pp. 324-343.
• [9] The Mozart Programming System, http://www.mozart-oz.org.2006