[ad_1]
The two computer scientists, Assistant Professor Jacob Holm from UCPH and Associate Professor Eva Rotenberg from DTU almost gave their solution in the summer of 2019, after submitting a research article that became the precursor to the article in which they finally solved the mathematical puzzle. Credit: University of Copenhagen
The researchers thought they were five years away from solving a mathematical puzzle from the 1980s. In fact, and without knowing it, they had almost solved the problem already.
Researchers at the University of Copenhagen and the Technical University of Denmark (DTU) thought they were five years away from solving a mathematical puzzle from the 1980s. In fact, and without knowing it, they had almost solved the problem. and had just unveiled much of the solution in a research article. The solution could be used to improve the phones and computers of tomorrow.
A real puzzle. This is how we can safely describe this mathematical problem in the discipline of graph theory. Two mathematicians from the Department of Computer Science and DTU at the University of Copenhagen have now solved a problem the world’s fastest and smartest have struggled with since the 1980s.
The two computer scientists, Assistant Professor Jacob Holm from UCPH and Associate Professor Eva Rotenberg from DTU almost gave their solution in the summer of 2019, after submitting a research article that became the precursor to the article in which they finally solved the mathematical puzzle.
“We had almost given up on getting the last piece and solving the puzzle. We thought we had a minor, interesting result that did not solve the problem in any way. We guessed that it would take another five years of work, at best, before we could solve the puzzle, ”says Jacob Holm, who is with BARC, the algorithms section of the computer science department at UCPH.
In 1913, a precursor of the now-solved mathematical puzzle was published in “The Strand Magazine” under the title “The Three Utilities Problem”. It made the magazine’s readers scratch their heads and think. In the problem, each of the three chalets must have water, gas and electricity, while the “lines” between the houses and water, electricity and gas may not cross – this which is not possible. Credit: University of Copenhagen
A solution between the lines
Simply put, the puzzle is how to connect a number of points in a graph without allowing the lines that connect them to intersect. And how, with a mathematical calculation – an algorithm – you can make changes to a vast “network of graphs” to ensure that no line intersects without having to start all over. Properties that can be used, among other things, to build huge road networks or the tiny guts of computers, where electrical circuits on circuit boards cannot intersect.
Jacob Holm has been interested in the mathematical puzzle since 1998, but the answer was only revealed while the two researchers read their previously submitted research paper. Meanwhile, the researchers have heard of a new mathematical technique that they believe could be applied to the problem.
“As we read our research article, we suddenly realized that the solution was before our eyes. Our next reaction was “oh no – we shot ourselves in the foot and gave the solution,” says Associate Professor Eva Rotenberg of DTU.
Can be used for computer electronics
It was at this point that the two researchers got busy writing the research paper and working out the details to solve the riddle that Holm had been working on intermittently since 1998.
“We worked tirelessly on the article, for five to six weeks. And it ended up filling more than 80 pages ”, explains Eva Rotenberg.
Fortunately, no one beat them to the solution and the two researchers were able to present their results at the main theoretical computer conferences, which were to be held in Chicago, but which ended up being held virtually.
So, what can the solution to this mathematical puzzle be for? The two researchers aren’t sure, but they have a few suggestions.
“Our research is basic research, so we rarely know what it will be used for. Even from the start, we find the applications difficult to imagine, ”says Jacob Holm, who adds:
“The design of microchips and printed circuits, which are found in all electronic devices, could be an area in which our result ends up being used. When you draw wires on a printed circuit board, they should never cross. Otherwise, short circuits will occur. The same goes for microchips, which contain millions of transistors and for which you have to have a graphic design. “
About graph theory
A GRAPH is a very simple construction used to model things that can be described as objects and the connections between them. Graph theory is both a field of mathematics and an important tool in computer science.
In this context, a graph can be illustrated by a diagram made up of a certain number of points (nodes, vertices) associated with a certain number of lines (edges). Each edge is shown as a line (or a curved part) with nodes as two ends.
About the solution
There are two types of updates in dynamic charts: one can remove an edge and you can insert a new edge. These two operations must be performed by the user, while an algorithm follows the network design at all times. This is the algorithm for which the researchers found the recipe.
Reference: “Fully dynamic polylogarithmic time planarity test” by Jacob Holm and Eva Rotenberg, December 10, 2019, Computer Science> Data structures and algorithms.
arXiv: 1911.03449
[ad_2]
Source link