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.

Plos One
|June 6, 2024
PubMed

Related Concept Videos

Theorems of Pappus and Guldinus: Problem Solving01:12

Theorems of Pappus and Guldinus: Problem Solving

Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
730
Heuristics01:21

Heuristics

Heuristics are problem-solving strategies that use mental shortcuts to simplify decision-making. Unlike algorithms, which must be followed precisely to achieve a correct result, heuristics offer a general problem-solving framework. They save time and energy but can sometimes lead to less rational decisions.
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...
84
Castigliano's Theorem: Problem Solving01:14

Castigliano's Theorem: Problem Solving

The deflection of a simply supported beam that carries a central point load can be analyzed using structural mechanics principles, particularly by applying Castigliano's theorem. This theorem relates the displacement at the load application point to the partial derivatives of the strain energy in the structure. The simply supported beam with a point load at its center has symmetric reaction forces at the supports, each bearing half of the load. The bending moment at any point along the beam...
634
Vector Algebra: Graphical Method01:10

Vector Algebra: Graphical Method

Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
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...
12.1K
The Availability Heuristic01:08

The Availability Heuristic

A heuristic is a general problem-solving framework (Tversky & Kahneman, 1974). You can think of these as mental shortcuts that are used to solve problems. Different types of heuristics are used in different types of situations, and the impulse to use a heuristic occurs when one of five conditions is met (Pratkanis, 1989):
5.9K
Normal and Tangetial Components: Problem Solving01:24

Normal and Tangetial Components: Problem Solving

Consider a man with a mass of 70 kg seated in a chair connected to a pin support through a member BC. If the man maintains an upright position, the task is to determine the horizontal and vertical reactions of the chair on the man when the member makes a 45° angle with the horizontal. At this moment, the man has a speed of 5 m/s, increasing at a rate of 1 m/s².
177