Related Experiment Video
Updated: Jun 24, 2025

Modeling the Functional Network for Spatial Navigation in the Human Brain
Published on: October 13, 2023
A heuristic method for solving the Steiner tree problem in graphs using network centralities
Misa Fujita1,2, Yutaka Shimada3, Takayuki Kimura4
1Department of Electrical and Electronic Engineering, School of Engineering, Chukyo University, Nagoya-shi, Aichi, Japan.
Abstract:
We propose a heuristic method of using network centralities for constructing small-weight Steiner trees in this paper. The Steiner tree problem in graphs is one of the practical NP-hard combinatorial optimization problems. Given a graph and a set of vertices called terminals in the graph, the objective of the Steiner tree problem in graphs is to find a minimum weight Steiner tree that is a tree containing all the terminals. Conventional construction methods make a Steiner tree based on the shortest paths between terminals. If these shortest paths are overlapped as much as possible, we can obtain a small-weight Steiner tree. Therefore, we proposed to use network centralities to distinguish which edges should be included to make a small-weight Steiner tree. Experimental results revealed that using the vertex or the edge betweenness centralities contributes to making small-weight Steiner trees.
More Related Videos
08:43Application of Granger Causality Analysis of the Directed Functional Connection in Alzheimer's Disease and Mild Cognitive Impairment
Published on: August 7, 2017
10:44Inherent Dynamics Visualizer, an Interactive Application for Evaluating and Visualizing Outputs from a Gene Regulatory Network Inference Pipeline
Published on: December 7, 2021
Related Concept Videos
Theorems of Pappus and Guldinus: Problem Solving
Heuristics
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
Castigliano's Theorem: Problem Solving
Vector Algebra: Graphical Method
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
The Availability Heuristic
Normal and Tangetial Components: Problem Solving