Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem

DOI10.7155/jgaa.00246zbMath1276.05030OpenAlexW2008864968MaRDI QIDQ5891346

Takeaki Uno, Ryuhei Uehara, Yota Otachi, Yoshio Okamoto

Publication date: 28 November 2013

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00246

zbMATH Keywords

spanning tree congestionconstant-factor approximation algorithm for cographslinear-time algorithm for chordal cographsnon-sparse graph classes

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

A Survey on Spanning Tree Congestion ⋮ Optimality computation of the minimum stretch spanning tree problem ⋮ Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition ⋮ The minimum stretch spanning tree problem for typical graphs

This page was built for publication: Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem