Marek Kubale

I am a Professor at

Gdansk University of Technology , ETI Faculty, Department of Algorithms and System Modeling
ul. Narutowicza 11/12, 80-233 Gdańsk, POLAND
Phone: +48 58 347 1818  Fax: +48 58 347 1766
Email: kubale@eti.pg.gda.pl
Place: building A of ETI Faculty, room 251

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:

American Mathematical Society

Institute of Combinatorics and its Applications

Committee of Informatics, Polish Academy of Sciences

Editorial Boards:

Networks (USA) (up to 2000)

DISCUSSIONES MATHEMATICAE - Graph Theory (Poland)

Decision Making in Manufacturing and Services (Poland)

ZESZYTY NAUKOWE POLITECHNIKI GDAŃSKIEJ (Poland)

Theses supervised:

Janusz Cielątkowski (1996): Modeling and Implementation of Algorithm for Finding Connections in Time Dependant Transportation Networks (in Polish).

Konrad Piwakowski (1996): Application of Algorithmic Methods in Finding Lower and Upper bounds for Ramsey Numbers (in Polish).

Krzysztof Manuszewski (1998): Algorithmically Hard-to-Color Graphs (in Polish).

Włodzimierz Głazek (1999): Algorithms for Scheduling Divisible Tasks on Parallel Machines.

Krzysztof Giaro (1999): Scheduling of Tasks without Two-Sided Waiting Periods on Dedicated Processors (in Polish).

Piotr Borowiecki (2000): On-Line Algorithms for Graph Coloring (in Polish).

Robert Janczewski (2001): T-coloring of Graphs and  its Applications (in Polish).

Michał Małafiejski (2002): Scheduling of Multiprocessor Tasks to Minimize Mean Flow Time (in Polish).

Dariusz Szyfelbein (2003): Methods of Local and Global Search of Solution Space for the Timetabling Problem (in Polish).

Paweł Żyliński (2004): Cooperative Guards Problem - Combinatorial Bounds and Complexity.

Adam Nadolski (2005): Chromatic Task Scheduling in Cyclic Production Systems (in Polish).

Hanna Furmańczyk (2005): Equitable and Cardinality Restricted Graph Coloring (in Polish).

Tomasz Dzido (2006): Ramsey Numbers for Various Classes of Graphs  (in Polish).

Łukasz Kuszner (2006): Distributed Graph Coloring (in Polish).

Dariusz Dereniowski (2006): Parallel Scheduling by Graph Ranking.

Paweł Obszarski (2009): Dedicated Scheduling of UET Tasks in Hypergraph Model (in Polish).

Jacek Dąbrowski (2009): Clonal Selection in Discrete Optimization.

Robert Fidytek (2010): Two and Three-color Ramsey Numbers for Paths and Cycles (in Polish).

Krzysztof Ocetkiewicz (2011): Time-Dependent Task Scheduling (in Polish).

Krzysztof Turowski (2015): Analysis of Algorithmic Properties of Backbone Coloring Problems (in Polish).

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: 

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, 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].

Miscellaneous

Avocations:

 Bridge, tennis.