Marek Kubale |
How to contact me:
I am a Professor atGdansk University of Technology , ETI Faculty, Department of Algorithms and System Modeling |
About myself
Address: | ul. Ujeścisko 18A m.4, 80-130 Gdańsk |
Qualifications: | 1969 - M.S.E.E. | |
| 1975 - Ph.D. | |
| 1989 - D.Sc. | |
| 1998 - Prof. | |
| 2001 - Full Professor | |
Habilitation Thesis: | Graph Coloring Methods and Their Application in Selected Technological Problems (in Polish) | |
Posts held: | 1975 - 1989 | - Assistant Professor, TU Gdańsk |
1990 - 1991 | - Associate Professor, Head of Department, TU Gdańsk | |
1991 - 2016 | - Professor, Head of Department, TU Gdańsk | |
1991 - | - Professor, University of Gdańsk | |
1999 - 2005 | - Associate Dean for Science, ETI Faculty | |
Experience: | Wide experience in design and analysis of computer algorithms. Duties include tuition to students in graph theory, operational research, discrete optimization and computational complexity. Special training in implementation and application of graph coloring algorithms and task scheduling algorithms. | |
No. of citations: | 430 (ISI – Cited Ref. Search) | |
Membership: | ||
| ||
| ||
Editorial Boards: | Networks (USA) (up to 2000) | |
Theses supervised: | 1. | Janusz Cielątkowski (1996): Modeling and Implementation of Algorithm for Finding Connections in Time Dependant Transportation Networks (in Polish). | ||||||||||||||||||||
2. | Konrad Piwakowski (1996): Application of Algorithmic Methods in Finding Lower and Upper bounds for Ramsey Numbers (in Polish). | |||||||||||||||||||||
3. | Krzysztof Manuszewski (1998): Algorithmically Hard-to-Color Graphs (in Polish). | |||||||||||||||||||||
4. | Włodzimierz Głazek (1999): Algorithms for Scheduling Divisible Tasks on Parallel Machines. | |||||||||||||||||||||
5. | Krzysztof Giaro (1999): Scheduling of Tasks without Two-Sided Waiting Periods on Dedicated Processors (in Polish). | |||||||||||||||||||||
6. | Piotr Borowiecki (2000): On-Line Algorithms for Graph Coloring (in Polish). | |||||||||||||||||||||
7. | Robert Janczewski (2001): T-coloring of Graphs and its Applications (in Polish). | |||||||||||||||||||||
8. | Michał Małafiejski (2002): Scheduling of Multiprocessor Tasks to Minimize Mean Flow Time (in Polish). | |||||||||||||||||||||
9. | Dariusz Szyfelbein (2003): Methods of Local and Global Search of Solution Space for the Timetabling Problem (in Polish). | |||||||||||||||||||||
10. | Paweł Żyliński (2004): Cooperative Guards Problem - Combinatorial Bounds and Complexity. | |||||||||||||||||||||
11. | Adam Nadolski (2005): Chromatic Task Scheduling in Cyclic Production Systems (in Polish). | |||||||||||||||||||||
12. | Hanna Furmańczyk (2005): Equitable and Cardinality Restricted Graph Coloring (in Polish). | |||||||||||||||||||||
13. | Tomasz Dzido (2006): Ramsey Numbers for Various Classes of Graphs (in Polish). | |||||||||||||||||||||
14. | Łukasz Kuszner (2006): Distributed Graph Coloring (in Polish). | |||||||||||||||||||||
15. | Dariusz Dereniowski (2006): Parallel Scheduling by Graph Ranking. | |||||||||||||||||||||
16. | Paweł Obszarski (2009): Dedicated Scheduling of UET Tasks in Hypergraph Model (in Polish). | |||||||||||||||||||||
17. | Jacek Dąbrowski (2009): Clonal Selection in Discrete Optimization. | |||||||||||||||||||||
18. | Robert Fidytek (2010): Two and Three-color Ramsey Numbers for Paths and Cycles (in Polish). | |||||||||||||||||||||
19. | Krzysztof Ocetkiewicz (2011): Time-Dependent Task Scheduling (in Polish). | |||||||||||||||||||||
20. | Krzysztof Turowski (2015): Analysis of Algorithmic Properties of Backbone Coloring Problems (in Polish). | |||||||||||||||||||||
21. | Anna Małafiejska (2016): Incidence Coloring of Graphs (in Polish). | |||||||||||||||||||||
Books: | M. Kubale, Introduction to Computational Complexity and Algorithmic Graph Coloring, Wydawnictwo GTN, Gdańsk 1998. | |||||||||||||||||||||
M. Kubale, Łagodne wprowadzenie do analizy algorytmów (in Polish), Wydawnictwo PG, Gdańsk 1999, 2002, 2004, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2016, 2017. | ||||||||||||||||||||||
M. Kubale et al.: Optymalizacja dyskretna. Modele i metody kolorowania grafów (in Polish), Wydawnictwa Naukowo-Techniczne, Warszawa 2002. | ||||||||||||||||||||||
M. Kubale et al.: Graph Colorings, American Mathematical Society, Providence, Rhode Island, 2004. | ||||||||||||||||||||||
Selected Recent Articles: | K. Giaro, M.Kubale, A note on polynomial al algorithm for cost coloring of bipartite graphs with ∆≤4, Discussiones Mathematicae Graph Theory, (2019), in press. | |||||||||||||||||||||
T. Pikies, M. Kubale, Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines, Bulletin of the Polish Academy of Sciences, 67 (2019), 31-36. | ||||||||||||||||||||||
H. Furmańczyk, M. Kubale, Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs, Discrete Applied Mathematics, 237 (2018), 116-122. [MR3763304]. | ||||||||||||||||||||||
H. Furmańczyk, M. Kubale, Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines, Discrete Applied Mathematics, 234 (2018), 210-217. [MR3736922]. | ||||||||||||||||||||||
M. Duraj, P. Kopeć, M. Kubale, T. Pikies, Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments, Decision Making in Manufacturing and Services, AGH, 11 (2017), 53-61. [MR3733168] . | ||||||||||||||||||||||
H. Furmańczyk, M. Kubale, Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines, Bulletin of the Polish Academy of Sciences – Technical Sciences, 65 (2017), 29 - 34. | ||||||||||||||||||||||
H. Furmańczyk, M. Kubale, V. V. Mkrtchyan, Equitable colorings of corona multiproduct of graphs, Disc. Math. Graph Theory, 37 (2017), 1079-1094. [MR3684127]. | ||||||||||||||||||||||
H. Furmańczyk, A. Jastrzębski, M. Kubale, Equitable coloring of graphs. Recent theoretical results and new practical algorithms, Archives Control Sciences, 26 (2016), 281-295. [MR3744255]. | ||||||||||||||||||||||
H. Furmańczyk, M. Kubale, St. Radziszowski, On bipartization of cubic graphs by removal of an independent set, Discrete Applied Mathematics, 209 (2016), 15–121. [MR3510435]. | ||||||||||||||||||||||
H. Furmańczyk, M. Kubale, Equitable coloring of corona products of cubic graphs is harder than ordinary coloring, Ars Mathematica Contemporanea, 10 (2016), 333-347. [MR3529295]. | ||||||||||||||||||||||
M. Jurkiewicz, M. Kubale, K. Ocetkiewicz, On the independence number of some strong products of cycle-Powers, Foundations of Computing and Decision Sciences, The Journal of Poznan University of Technology, 40 (2015), 133–141. [MR3410566]. | ||||||||||||||||||||||
P. Obszarski, A. Jastrzębski, M. Kubale, Towards the boundary between easy and hard control problems in multicast Clos networks, Bulletin of the Polish Academy of Sciences – Technical Sciences, 63 (2015), 739-744. | ||||||||||||||||||||||
H. Furmańczyk, M. Kubale, Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling, Archives Control Sciences, 25 (2015), 109-116. [MR34345478]. | ||||||||||||||||||||||
M. Jurkiewicz, M. Kubale, K. Turowski, Some lower bounds on the Shannon capacity, Journal of Applied Computer Science, 22 (2014), 31-42. | ||||||||||||||||||||||
H. Furmańczyk, K. Kaliraj, M. Kubale, J.V. Vivin, Equitable coloring of corona products of graphs, Adv. App. Disc. Math., 11, No. 2, (2013), 103-120. [MR3099949]. | ||||||||||||||||||||||
M. Kubale, Modele i metody kolorowania grafów. Część II. Przegląd Elektrotechniczny 88 (2012), 51-55. | ||||||||||||||||||||||
M. Kubale, Million Dollar Algorithm? Academia 29 (2011), 32-35. | ||||||||||||||||||||||
M. Jurkiewicz, M. Kubale, A note on Shannon capacity for invariant and evolving channels, Journal of Applied Computer Science 19 (2011), 19-29. | ||||||||||||||||||||||
M. Kubale, Modele i metody kolorowania grafów. Część I. Przegląd Elektrotechniczny 86 (2010), 115-117. | ||||||||||||||||||||||
M. Kubale, K. Ocetkiewicz, A new optimal algorithm for a time-dependent scheduling problem, Control and Cybernetics 38 (2009), 713-721. [MR2650362J]. | ||||||||||||||||||||||
K. Giaro, M. Kubale, Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs, Disc. Math. Graph Theory 29 (2009), 361-376. [MR#11i: 05073]. | ||||||||||||||||||||||
K. Giaro, M. Kubale, P. Obszarski, A graph coloring approach to scheduling multiprocessor task on dedicated machines with availability constrains, Disc. Appl. Math. 157 (2009), 3625-3630. [MR#10k: 05299]. | ||||||||||||||||||||||
D. Dereniowski, M. Kubale, Program verification strategy and edge ranking of graphs, Polish Journal of Environmental Studies 17, 2A (2008), 124-128. | ||||||||||||||||||||||
T. Dzido, M. Kubale, K. Piwakowski, On some Ramsey and Turán-type numbers for paths and cycles, Electr. J. of Comb. 13 (2006), #55. [MR#07d: 05108]. | ||||||||||||||||||||||
H. Furmańczyk, K. Giaro, M. Kubale, Equitable 4-coloring of cacti and edge-cacti in polynomial time, Int. J. Pure Appl Mathematics 27 (2006), 377-389. [MR2219570] | ||||||||||||||||||||||
K. Giaro, M. Kubale, Chromatic scheduling of 1- and 2-processor UET tasks on dedicated machines with availability constraints, LNCS 3911 (2006), 855-862. | ||||||||||||||||||||||
D.Dereniowski, M.Kubale, Parallel query processing and edge ranking of graphs, LNCS 3911 (2006), 463-469. | ||||||||||||||||||||||
D.Dereniowski, M.Kubale, Efficient parallel query processing by graph ranking, Fundamenta Informaticae 69 (2006), 273-285. [MR#08f: 68024] | ||||||||||||||||||||||
M. Małafiejski, K. Giaro, R. Janczewski, M. Kubale, Sum coloring of bipartite graphs with bounded degree, Algorithmica 40 (2004), 235-244. | ||||||||||||||||||||||
D. Dereniowski, M. Kubale, Cholesky factorization of matrices in parallel and ranking of graphs, LNCS 3019 (2004), 985-992 . | ||||||||||||||||||||||
Giaro K., Kubale M., Piwakowski K.: Complexity results on open shop scheduling to minimize total cost of operations, Int. J. Comp. Sys. Sign. 3 (2002), 84-91. | ||||||||||||||||||||||
K. Giaro, R. Janczewski, M. Kubale, M. Małafiejski, A 27/26-approximation algorithm for the chromatic sum coloring of bipartite graphs, LNCS 2462 (2002), 135-145. [MR2091822] | ||||||||||||||||||||||
K. Giaro, M. Kubale, M. Małafiejski, K. Piwakowski, Dedicated scheduling of biprocessor tasks to minimize mean flow time, LNCS 2328 (2002), 87-96. | ||||||||||||||||||||||
M. Kubale, K. Manuszewski, K. Giaro, On the smallest hard to color sequentially graph, Cong. Numer. 150 (2001), 155-160. [MR#02m: 05088] | ||||||||||||||||||||||
K. Giaro, M. Kubale, M. Małafiejski, Consecutive colorings of the edges of general graphs, Disc. Math. 236 (2001), 131-143. [MR#02a: 05100] | ||||||||||||||||||||||
R. Janczewski, M. Kubale, K. Manuszewski, K. Piwakowski, The smallest hard-to-color graph for algorithm DSATUR, Disc. Math. 236 (2001), 151-165. [MR#02a: 05231] | ||||||||||||||||||||||
K. Giaro, M. Kubale, Edge-chromatic sum of trees and bounded cyclicity graphs, Inf. Prosess. Lett. 75 (2000), 65-69. [MR#01g: 68041] | ||||||||||||||||||||||
Miscellaneous | ||||||||||||||||||||||
Avocations: | Bridge, tennis. | |||||||||||||||||||||