News and events - Tampere University of Technology

Complexity theory restricts computer-assisted design of communication networks

Graph-theoretical colouring problems are a key tool for modeling real-world telecommunications problems. In his doctoral thesis, MSc (Tech) Juho Lauri studied the computational complexity of these problems.

Several real-world problems are modeled as graphs. For instance, the GPS system of a car models every intersection of a road network as a point and each road segment between two intersections as a line. Road networks are extensive, and users want to quickly determine the shortest route to their destination.

“Graph problems are often solved using a computer. However, graphs modeling real-world phenomena are often so massive that computation must be performed efficiently. Some problems are computationally so demanding that not even a supercomputer can solve them in a reasonable amount of time,” Juho Lauri explains.

The efficiency of the solver program thus plays a key role.

“When the performance of the computing device falls short, our only hope is to speed up the solver program. When unable to do that, it is crucial to know if we have hit a theoretical obstacle, Lauri continues.

An important subfield of graph theory is formed by graph colouring. Graph colouring problems are key to modeling real-world problems arising from the domain of data transfer and telecommunications. In his research, Juho Lauri studied a particular graph colouring problem that can be used to model message routing in a network, for example. A particularly important theme is computational complexity. The main results of the work explain precisely just how quickly a computer can solve some graph coloring problems, Lauri says. In his work, Lauri applied modern theoretical tools from the field of complexity theory.

“These research findings tell us exactly how quickly a computer is able to solve particular colouring problems,” Lauri summarises.

Prior to his dissertation, Lauri studied colouring problems in his master’s thesis, which also merited him the 2014 thesis award granted by Tietojenkäsittelytieteen Seura ry (Finnish Society for Computer Science).

Public defence of a doctoral dissertation on Thursday, 3 November 2016

MSc (Tech) Juho Lauri’s doctoral dissertation in the field of theoretical computer science entitled ‘Chasing the Rainbow Connection: Hardness, Algorithms, and Bounds’ will be publicly examined at the Faculty of Natural Sciences of Tampere University of Technology (TUT) in room TB224 in the Tietotalo building (Korkeakoulunkatu 1, Tampere) at 12 noon on Thursday, 3 November 2016. The opponent will be Professor Pinar Heggernes (University of Bergen, Norway). Professor Tapio Elomaa from the Department of Mathematics at TUT will act as Chairman.

Juho Lauri (28) comes from Kurikka, Finland, and works in the Department of Mathematics at TUT.

The dissertation is available online at: http://urn.fi/URN:ISBN:978-952-15-3842-1

Further information: Juho Lauri, juho.lauri@tut.fi

News submitted by: Tiina Leivo
Keywords: science and research