The spanning tree congestion problem on interval graphs

DOI10.1016/J.DAM.2025.06.054MaRDI QIDQ6928010zbMATH OpenFDO

Authors Lan Lin, Yixun Lin

Publication date 17 September 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.06.054

zbMATH Keywords

fundamental edge-cutinterval graphspanning tree congestionspanning tree optimization

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• A Survey on Spanning Tree Congestion
• Algorithmic graph theory and perfect graphs
• Graph theory
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem
• Minimal congestion trees
• Minimum congestion spanning trees in planar graphs
• Minimum congestion spanning trees of grids and discrete toruses
• On spanning tree congestion of graphs
• On tree congestion of graphs
• Optimality computation of the minimum stretch spanning tree problem
• Parameterized complexity of the spanning tree congestion problem
• Spanning tree congestion of k-outerplanar graphs
• Spanning tree congestion of rook's graphs
• Tree 3-spanners on interval, permutation and regular bipartite graphs

This page was built for publication: The spanning tree congestion problem on interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6928010)