Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Zastosowanie programowania z więzami do generowania grafów całkowitych bez ± 1 w spektrum
Języki publikacji
Abstrakty
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).
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.
Czasopismo
Rocznik
Tom
Strony
105--114
Opis fizyczny
Bibliogr. 9 poz., rys., tab.
Twórcy
autor
autor
autor
- Poznan University of Technology, pl. M. Skłodowskiej-Curie 5, 60-965 Poznań, Poland, zwierzak@man.poznan.pl
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
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BPC6-0001-0007