Show simple item record

dc.contributor.authorBodlaender, Hans L.
dc.contributor.authorFomin, Fedor
dc.contributor.authorGolovach, Petr
dc.contributor.authorOtachi, Yota
dc.contributor.authorvan Leeuwen, Erik Jan
dc.PublishedBodlaender HL, Fomin V, Golovach P, Otachi Y, van Leeuwen EJ. Parameterized complexity of the spanning tree congestion problem. Algorithmica. 2012;64(1):85-111eng
dc.description.abstractWe study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k≥8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for k≤3 the problem becomes polynomially time solvable.en_US
dc.rightsAttribution CC BY-NCeng
dc.subjectSpanning tree congestioneng
dc.subjectGraph minoreng
dc.subjectParameterized algorithmseng
dc.subjectApex grapheng
dc.titleParameterized complexity of the spanning tree congestion problemen_US
dc.typePeer reviewed
dc.typeJournal article
dc.rights.holderCopyright 2011 The Author(s)en_US
dc.subject.nsiVDP::Matematikk og naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Algoritmer og beregnbarhetsteori: 422
dc.subject.nsiVDP::Mathematics and natural scienses: 400::Information and communication science: 420::Algorithms and computability theory: 422

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution CC BY-NC
Except where otherwise noted, this item's license is described as Attribution CC BY-NC