Research areas

My research focuses on Algorithmic and Structural Graph Theory and Combinatorial Optimization. More specifically, I have been working on the following topics:

Graph classes, Computational complexity of graph problems, Generelized graph coloring (e.g. Split-coloring, Cocoloring, Defective coloring, (p,k)-coloring, Polar graphs, Selective-coloring), Matching Theory (Minimum maximal matching, Equimatchable graphs, Induced Matchings), Domination Problems, IP formulation based methods to solve graph problems.

Publications

Publications in referred journals

1. T.Ekim and Th.V.Paschos, Approximation preserving reductions among set covering and vertex covering hierarchies via differential approximation ratio, International Journal of Computer Mathematics, 81, 5, pages 569 - 582, 2004. (SCI-E)

2. M. Demange, T.Ekim, D. de Werra, (p,k)-coloring problems in line graphs, Theoretical Computer Science, 349: 462-474, 2005. (SCI)

3. M. Demange, T.Ekim, D. de Werra, Partitioningcographs into cliques and stable sets, Discrete Optimization, 2:145-153, 2005. (SCI-E)

4. T.Ekim and D. de Werra, On split-coloring problems, Journal of Combinatorial Optimization, 10: 211-225, 2005. (SCI-E)

5. D. de Werra, T.Ekim, C.Raess, Construction of sports schedules with multiple venues, Discrete Applied Mathematics, 154:47-58, 2006. (SCI)

6. M. Demange, T.Ekim, D. de Werra, On the approximation of Min Split-coloring and Min Cocoloring, Journal of Graph Algorithms and Applications, 10(2): 297-315, 2006.

7. T.Ekim, N.V.R. Mahadev, D. de Werra, Polarcographs, Discrete Applied Mathematics, 156(10), 1652-1660, 2008. (SCI)

8. T.Ekim, P. Hell, J.Stacho, D. de Werra, Polarity of chordal graphs, Discrete Applied Mathematics, 156 (13), 2469-2479, 2008. (SCI)

9. T.Ekim, A. Geinoz, D. de Werra, Construction of balanced sports schedules using partitions intosubleagues, Operational Research Letters, 36:3, 279-282, 2008. (SCI)

10. M. Demange, T.Ekim, D. de Werra, A tutorial on the use of graph coloring models for some problems in robotics, European Journal of Operational Research, 192 (1), 41-55, 2009. (SCI-E)

11.  T.Ekim, J. Gimbel, Partitioning graphs into complete and empty graphs, Discrete Mathematics, 309 (2009), 5849-5856. (SCI)

12. T.Ekim, J. Hoang, Recognizing line-polar bipartite graphs in time O(n), Discrete Applied Mathematics 158 (2010) 1593-1598. (SCI)

13. T.Ekim, B. Ries, D. de Werra, Split-critical and uniquely colorable graphs, Discrete Mathematics and Theoretical Computer Science, 12:5 (2010), 1-24. (SCIE)

14. T.Ekim, C. Taşkın, Integer Programming Formulations for the Weighted Minimum Maximal Matching Problem, Optimization Letters, Volume 6, Issue 6 (2012), Page 1161-1171. (SCI-E)

15. T.Ekim, J. Gimbel, Some defective parameters in graphs, Graphs and Combinatorics, DOI : 10.1007/s00373-011-1111-5 Volume 29, Number 2, (2013), 213-224. (SCI-E)

16. T.Ekim, P. Heggernes, D. Meister, Polar permutation graphs are polynomial time recognizable, European Journal of Combinatorics, DOI : 10.1016/j.bbr.2011.03.031.34 (2013) 576-592 (SCI)

17. M. Bodur, T.Ekim, C. Taskin, Decomposition algorithms for solving the minimum weight maximal matching problem, Networks, Volume 62, Issue 4, Pages 273-287, December 2013, DOI: 10.1002/net.21516. (SCI)

18. M. Demange, T.Ekim, A note on the NP-hardness of two matching problems in induced subgrids, Discrete Mathematics and Theoretical Computer Science, 15:2 (2013), 233-242. (SCI-E)

19. F. Bonomo, D. Cornaz, T.Ekim, B. Ries, Perfectness of clustered graphs, Discrete Optimization, 10 (Nov 2013) 296-303. DOI: 10.1016/j.disopt.2013.07.006. (SCI-E)

20. M. Demange, T.Ekim, Efficient recognition ofequimatchable graphs, Information Processing Letters, 114 (Jan-Feb 2014), 66-71. DOI: 10.1016/j.ipl.2013.08.002. (SCI-E)

21. M. Demange, T.Ekim, C. Tanasescu, Hardness and Approximation of Minimum Maximal Matching, Int. J. of Computer Mathematics, Vol. 91, No. 8, 1635-1654, (September 2014) http://dx.doi.org/10.1080/00207160.2013.853052 (SCI-E)

22. T.Ekim, A. Erey, Block Decomposition Approach to Compute a Minimum Geodetic Set, RAIRO-Operations Research, 48:4 (June 2014), 497-507. DOI: 10.1051/ro/2014019. (SCI-E)

23. T.Ekim, M. Demange, C. Tanasescu, B. Ries, On Some Applications Of The Selective Graph Coloring Problem, European Journal of Operational Research, 240(2), (Jan 2015), 307-314. DOI: 10.1016/j.ejor.2014.05.011. (SCI-E)

24. A. Akdemir, T.Ekim, Advances on Defective Parameters in Graphs, Discrete Optimization, 16 (May 2015), 62-69. DOI:10.1016/j.disopt.2015.01.002. (SCI-E)

25. A. Boyaci, T.Ekim, M. Shalom, S. Zaks, Graphs of edge intersecting and non-splitting paths in a tree: Representations of holes Part I, Discrete Applied Mathematics, Volume 215, (31 December 2016), Pages 47-60, DOI: 10.1016/j.dam.2015.07.024. (SCI)

26. M. Demange, T.Ekim, B. Ries, On minimum and maximum selective graph coloring in several graph classes, Discrete Applied Mathematics, Volume 204, (May 2016), Pages 77-89, doi: 10.1016/j.dam.2015.10.005. (SCI)

27. A. Boyaci, T.Ekim, M. Shalom, The Maximum Cardinality Cut Problem in Co-bipartite Chain Graphs, Journal of Combinatorial Optimization, 35(1), (Jan 2018), 250-265. DOI: 10.1007/s10878-015-9963-x. (SCI-E)

28. A. Boyaci, T.Ekim, M. Shalom, S. Zaks, Graphs of Edge-Intersecting and Non-Splitting Paths, Theoretical Computer Science, 629, (23 May 2016), Pages 40-50, doi:10.1016/j.tcs.2015.10.004. (SCI)

29. C. Dibek, T.Ekim, D. Gozupek, M. Shalom, Equimatchable graphs are C2k+1-free for k >= 4, Discrete Mathematics, 339 (4 July 2016), pp. 2964-2969. doi: 10.1016/j.disc.2016.06.003

30. N. Chiarelli, C. Dibek, T. Ekim, D. Gozupek, S.Miclavic, On matching extendability of lexicographic products, RAIRO - Operations Research, 51 (2017) 857-873.doi: 10.1051/ro/2016072.

31. A. Boyaci, T.Ekim, M. Shalom, A Polynomial Time Algorithm for the Maximum Cardinality Cut Problem in Proper Interval Graphs, Information Processing Letters, 121 (May 2017) 29-33,doi: 10.1016/j.ipl.2017.01.007.

32. C. Dibek, T.Ekim, P. Heggernes, Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded, Discrete Mathematics, 340 (2017) 927-934. doi:10.1016/j.disc.2017.01.010.

33.  P. Abedin, S. Akbari, M. Demange, T. Ekim, Complexity of the improper twin edge coloring of graphs, Graphs and Combinatorics, 33:4 (July 2017) 595-615.

34. A. Boyaci, T.Ekim, M. Shalom, S. Zaks, Graphs of Edge-Intersecting and Non-Splitting One-Bend Paths in a Grid, Discrete Mathematics and Theoretical Computer Science, 19:1 (June 2017) no13.

35. Z. Deniz, T.Ekim, T. Hartinger, M. Milanic, M. Shalom, On two extensions of equimatchable graphs, Discrete Optimization, 26 (2017) 112-130.doi: 10.1016/j.disopt.2017.08.002.

36. B.Ahat, T. Ekim, C. Taskin, Integer Programming Formulations and Benders Decomposition for Maximum Induced Matching Problem, INFORMS Journal on Computing, 30(1), pp. 43--56, 2018.

37. A. Boyaci, T.Ekim, M. Shalom, S. Zaks, Graphs of edge intersecting and non-splitting paths in a tree: Representations of holes Part II, Discrete Mathematics and Theoretical Computer Science, 20:1, (Jan 2018), no2.

38.  S. Akbari, H.Alizadeh, T.Ekim, D. Gozupek, M. Shalom, Equimatchable claw-free graphs, Discrete Mathematics 341 (2018) 2859-2871.

39. T.Ekim, D. Gozupek, A. Hujdurovic, M. Milanic, On almost well-covered graphs of girth at least 6, Discrete Mathematics and Theoretical Computer Science, 20:2 (2018), 17.

40. O.Seker, T. Ekim, Z.C. Taskin, A Decomposition Approach to Solve the Selective Graph Coloring Problem in Some Perfect Graph Families, Networks, 73 (2019) 145-169. DOI: 10.1002/net.21850.

41. Z. Deniz, T. Ekim, Edge-Stable Equimatchable graphs, Discrete Applied Mathematics, Special Issue GO X, 261 (2019) 136-147.

42. T. Ekim, J. Gimbel, O. Seker, Small 1-Defective Ramsey Numbers in Perfect Graphs, Discrete Optimization, 34 (2019) 100548.

43. T. Ekim, A. Farley, A. Proskurowski, The complexity of the defensive domination problem in special graph classes, Discrete Mathematics, 343(2) (2020), 111665.

44. T. Ekim, M. Shalom, O. Şeker, The complexity of Subtree Intersection Representation of Chordal Graphs and Linear Time Chordal Graph Generation, arxiv.

45. S. Akbari, T. Ekim, A.H. Ghodrati, S. Zare, Well-indumatched trees and graphs of bounded girth, arxiv.

 

 Publications in referred conference proceedings

1. M. Demange, T.Ekim, D. de Werra, (p; k)-coloring problems in line graphs, Extended Abstract, GRACO 2005, Electronic Notes in Discrete Mathematics volume 19, pages 49-55, 2005.

2. T.Ekim, N.V.R. Mahadev, D. de Werra, Polarcographs, Extended Abstract, Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Electronic Notes in Discrete Mathematics, volume 28, pages 317- 323, 2007.

3. M. Demange, T.Ekim, Minimum maximal matching is NP-hard in regular bipartite graphs, Proceedings of Theory and Applications of Models of Computation, TAMC 2008, LNCS 4978, 364-374, 2008.

4. T.Ekim, P. Heggernes, D. Meister, Polar permutation graphs, J.Fiala, J.Kratochvil, and M. Miller (eds.): IWOCA 2009, LNCS 5874, pp 218 - 229, 2009.

5. T.Ekim, A. Erey, P. Heggernes, P. Hof, D. Meister, Computing minimum geodetic sets in proper interval graphs, LATIN 2012, LNCS 7256, pp 279-290, 2012.

6. R.M. Yuzsever, T.Ekim, N. Aras, A Branch-and-Price Algorithm for Split-Coloring Problem, Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012), pp. 249-253, May 29-31, 2012, Germany.

7. A.Boyaci, T.Ekim, M. Shalom, S. Zaks, Graphs of edge intersecting and non-splitting paths in a tree: towards hole representations, Proceedings of Workshop on Graphs WG 2013, June 19-21, 2013, Germany, Lecture Notes in Computer Science 8165, 115-126, 2013.

8. B. Basciftci, U. B. Nazlican, F. Alagoz, T.Ekim, Satış Rotalaması için tamsayılı programlama formülasyonları, Üretim Araştırmaları Sempozyumu, 25 - 27 Eylül 2013, Sakarya Üniversitesi, Sayfa 706-712, 2013. (3rd place in the student project contest of UAS)

9. A. Boyaci, T.Ekim, M. Shalom, S. Zaks, Graphs of edge intersecting and non-splitting paths, Proceedings of the 15th Italian Conference on Theoretical Computer Science ICTCS 2014, pp. 45-58, Perugia, Italy, September 17-19, 2014. (available online at http://ceur-ws.org/Vol-1231)

10.  M. Demange, T.Ekim, B. Ries, On the Minimum and Maximum Selective Graph Coloring Problems, Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2015), pp 189-192, Eds. AliFuat Alkaya,EkremDuman, May 26-28, 2015, Turkey.

11.  C. Dibek, T. Ekim, D. Gozupek, M. Shalom,Equimatchable Graphs are C2k+1-free for k 4, Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2015), pp 125-128, Eds. AliFuatAlkaya, EkremDuman, May 26-28, 2015, Turkey.

12.  Z. Deniz, T. Ekim, T. R. Hartinger, M. Milanic, M. Shalom, On Three Extensions ofEquimatchable Graphs, Electronic Notes in Discrete Mathematics, Volume 55, November 2016, Pages 177-180. doi: 10.1016/j.endm.2016.10.044. Proceedings of the 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2016), pp 182-185, Eds. A. Ceselli, R.Cordone, G. Righini (Eds.), June 6-8, 2016, Italia.(available online at http://ctw16.di.unimi.it/CTW16_Proceedings.pdf)

13.  Z. Deniz, T. Ekim, Characterization of StableEquimatchable graphs, Proceedings of the Bordeaux Graph Workshop, 2016, Pages 105-108. Available online: http://bgw.labri.fr/2016/bgw2016-booklet.pdf.

14.  O. Seker, P. Heggernes, T.Ekim, Z.C. Taskin, Linear-time generation of random chordal graphs, Proceedings of the 10th International Conference on Algorithms and Complexity, CIAC 2017, LNCS 10236, 442-453, 2017.

15. T. Ekim, M. Shalom, O. Seker, The Complexity of Subtree Intersection Representation of Chordal Graphs and Linear Time Chordal Graph Generation, International Symposium on Experimental Algorithms SEA 2019: Analysis of Experimental Algorithms, LNCS 11544, 21-34, 2019.

 Book Chapters

1. M. Demange, T.Ekim, D. de Werra, On the approximation of Min Split-coloring and Min Cocoloring, Annales du LAMSADE, No:4-5, October 2005.

Editor

1. Lecture Notes on Computer Science 6058, Structural Information and Communication Complexity, SIROCCO 2010.

Data

Click here for more information about my research on defective Ramsey numbers and other defective parameters in graphs as well as some online available sources.

This link contains a set of randomly generated chordal graphs obtained in our paper. Generation of random chordal graphs using subtrees of a Tree O. Seker, P. Heggernes, T. Ekim, Z. C.Taşkın,arxiv link here.

The problem instances (randomly generated chordal graphs, permutation graphs and generalized split graphs) and the source code used in our paper (O.Seker, T. Ekim, Z.C. Taskin, A Decomposition Approach to Solve the Selective Graph Coloring Problem in Some Perfect Graph Families, Networks, 2018, in press) are available here

Here, we provide our algorithm for random perfect graph generation and the large collection of randomly generated perfect graph instances obtained within our work (O.Seker, T.Ekim, Z.C. Taşkın, An Exact Cutting Plane Algorithm to Solve the Selective Graph Coloring Problem in Perfect Graphs). They can be used to test various algorithms designed for perfect graphs.

Instances for Maximum Weight Induced Matching can be found here

Instances for Minimum Weight Maximal Matching can be found here: medium size instances  and large instance

Research Visits