• HOME
  • NEWS
  • EXPLORE
    • CAREER
      • Companies
      • Jobs
    • EVENTS
    • iGEM
      • News
      • Team
    • PHOTOS
    • VIDEO
    • WIKI
  • BLOG
  • COMMUNITY
    • FACEBOOK
    • INSTAGRAM
    • TWITTER
Tuesday, August 5, 2025
BIOENGINEER.ORG
No Result
View All Result
  • Login
  • HOME
  • NEWS
  • EXPLORE
    • CAREER
      • Companies
      • Jobs
        • Lecturer
        • PhD Studentship
        • Postdoc
        • Research Assistant
    • EVENTS
    • iGEM
      • News
      • Team
    • PHOTOS
    • VIDEO
    • WIKI
  • BLOG
  • COMMUNITY
    • FACEBOOK
    • INSTAGRAM
    • TWITTER
  • HOME
  • NEWS
  • EXPLORE
    • CAREER
      • Companies
      • Jobs
        • Lecturer
        • PhD Studentship
        • Postdoc
        • Research Assistant
    • EVENTS
    • iGEM
      • News
      • Team
    • PHOTOS
    • VIDEO
    • WIKI
  • BLOG
  • COMMUNITY
    • FACEBOOK
    • INSTAGRAM
    • TWITTER
No Result
View All Result
Bioengineer.org
No Result
View All Result
Home NEWS Science News

Danish computer scientist has developed a superb algorithm for findin

Bioengineer by Bioengineer
March 10, 2021
in Science News
Reading Time: 4 mins read
0
Share on FacebookShare on TwitterShare on LinkedinShare on RedditShare on Telegram

IMAGE

Credit: University of Copenhagen

One of the most classic algorithmic problems deals with calculating the shortest path between two points. A more complicated variant of the problem is when the route traverses a changing network–whether this be a road network or the internet. For 40 years, an algorithm has been sought to provide an optimal solution to this problem. Now, computer scientist Christian Wulff-Nilsen of the University of Copenhagen and two research colleagues have come up with a recipe.

When heading somewhere new, most of us leave it to computer algorithms to help us find the best route, whether by using a car’s GPS, or public transport and map apps on their phone. Still, there are times when a proposed route doesn’t quite align with reality. This is because road networks, public transportation networks and other networks aren’t static. The best route can suddenly be the slowest, e.g. because a queue has formed due to roadworks or an accident.

People probably don’t think about the complicated math behind routing suggestions in these types of situations. The software being used is trying to solve a variant for the classic algorithmic “shortest path” problem, the shortest path in a dynamic network. For 40 years, researchers have been working to find an algorithm that can optimally solve this mathematical conundrum. Now, Christian Wulff-Nilsen of the University of Copenhagen’s Department of Computer Science has succeeded in cracking the nut along with two colleagues.

“We have developed an algorithm, for which we now have mathematical proof, that it is better than every other algorithm up to now–and the closest thing to optimal that will ever be, even if we look 1000 years into the future,” says Associate Professor Wulff-Nilsen. The results were presented at the prestigious FOCS 2020 conference.

Optimally, in this context, refers to an algorithm that spends as little time and as little computer memory as possible to calculate the best route in a given network.
This is not just true of road and transportation networks, but also the internet or any other type of network.

Networks as graphs

The researchers represent a network as a so-called dynamic graph”. In this context, a graph is an abstract representation of a network consisting of edges, roads for example, and nodes, representing intersections, for example. When a graph is dynamic, it means that it can change over time. The new algorithm handles changes consisting of deleted edges–for example, if the equivalent of a stretch of a road suddenly becomes inaccessible due to roadworks.

“The tremendous advantage of seeing a network as an abstract graph is that it can be used to represent any type of network. It could be the internet, where you want to send data via as short a route as possible, a human brain or the network of friendship relations on Facebook. This makes graph algorithms applicable in a wide variety of contexts,” explains Christian Wulff-Nilsen.

Traditional algorithms assume that a graph is static, which is rarely true in the real world. When these kinds of algorithms are used in a dynamic network, they need to be rerun every time a small change occurs in the graph–which wastes time.

More data necessitates better algorithms

Finding better algorithms is not just useful when travelling. It is necessary in virtually any area where data is produced, as Christian Wulff-Nilsen points out:

“We are living in a time when volumes of data grow at a tremendous rate and the development of hardware simply can’t keep up. In order to manage all of the data we produce, we need to develop smarter software that requires less running time and memory. That’s why we need smarter algorithms,” he says.

He hopes that it will be possible to use this algorithm or some of the techniques behind it in practice, but stresses that this is theoretical evidence and first requires experimentation.

###

FACTS:

  • The research article “Near-Optimal Decremental SSSP in Dense Weighted Digraphs” was presented at the prestigious FOCS 2020 conference.
  • The article was written by Christian Wulff-Nilsen, of the University of Copenhagen’s Department of Computer Science, and former Department of Computer Science PhD student Maximillian Probst Gutenberg and assistant professor Aaron Bernstein of Rutgers University.
  • The version of the “shortest path” problem that the researchers solved is called “The Decremental Single-Source Shortest Path Problem”. It is essentially about maintaining the shortest paths in a changing dynamic network from one starting point to all other nodes in a graph. The changes to a network consist of edge removals.
  • The paper gives a mathematical proof that the algorithm is essentially the optimal one for dynamic networks. On average, users will be able to change routes according to calculations made in constant time.
  • Media Contact
    Christian Wulff-Nilsen
    [email protected]

    Original Source

    https://www.science.ku.dk/english/press/news/2021/classic-math-conundrum-solved-danish-computer-scientist-has-developed-a-superb-algorithm-for-finding-the-shortest-route/

    Tags: Algorithms/ModelsCalculations/Problem-SolvingComputer ScienceMathematics/StatisticsResearch/DevelopmentRobotry/Artificial IntelligenceSoftware EngineeringTechnology/Engineering/Computer ScienceTheory/Design
    Share12Tweet8Share2ShareShareShare2

    Related Posts

    blank

    Over 150 Hospitals Nationwide Honored for Excellence in Comprehensive Cardiovascular Care

    August 5, 2025
    blank

    Debunking the Popular Theory of Ancient Psychedelic Mysteries

    August 5, 2025

    New Nomogram Outperforms ATA Risk Model

    August 5, 2025

    Repeated Exposure Reduces Moral Condemnation of Fake News

    August 5, 2025
    Please login to join discussion

    POPULAR NEWS

    • blank

      Neuropsychiatric Risks Linked to COVID-19 Revealed

      73 shares
      Share 29 Tweet 18
    • Overlooked Dangers: Debunking Common Myths About Skin Cancer Risk in the U.S.

      61 shares
      Share 24 Tweet 15
    • Predicting Colorectal Cancer Using Lifestyle Factors

      46 shares
      Share 18 Tweet 12
    • Dr. Miriam Merad Honored with French Knighthood for Groundbreaking Contributions to Science and Medicine

      47 shares
      Share 19 Tweet 12

    About

    We bring you the latest biotechnology news from best research centers and universities around the world. Check our website.

    Follow us

    Recent News

    Over 150 Hospitals Nationwide Honored for Excellence in Comprehensive Cardiovascular Care

    Debunking the Popular Theory of Ancient Psychedelic Mysteries

    New Nomogram Outperforms ATA Risk Model

    • Contact Us

    Bioengineer.org © Copyright 2023 All Rights Reserved.

    Welcome Back!

    Login to your account below

    Forgotten Password?

    Retrieve your password

    Please enter your username or email address to reset your password.

    Log In
    No Result
    View All Result
    • Homepages
      • Home Page 1
      • Home Page 2
    • News
    • National
    • Business
    • Health
    • Lifestyle
    • Science

    Bioengineer.org © Copyright 2023 All Rights Reserved.