• The spanning tree congestion p...

Treffer: The spanning tree congestion problem on interval graphs.

Title:
The spanning tree congestion problem on interval graphs.
Authors:
Lin, Lan1 (AUTHOR) linlan@tongji.edu.cn, Lin, Yixun2 (AUTHOR)
Source:
Discrete Applied Mathematics. Dec2025, Vol. 377, p147-153. 7p.
Subject Terms:
*SPANNING trees, *POLYNOMIAL time algorithms, *NP-hard problems, *ALGORITHMS, *INTERSECTION graph theory, *PARAMETERIZATION, *GRAPH theory
Database:
Academic Search Index

Weitere Informationen

The spanning tree congestion problem on a graph G asks for finding a spanning tree T of G such that the maximum size of a fundamental edge-cut with respect to T is minimized. There has been extensive study on the algorithmic aspects, such as the NP-hardness, fixed-parameter solvability, and exact results of special graph classes. A recent survey posted an open problem about the polynomial solvability of the spanning tree congestion problem on interval graphs. This paper gives a confirmative answer by presenting a polynomial-time algorithm. [ABSTRACT FROM AUTHOR]