dc.contributor.author | Bodlaender, Hans L. | |
dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Golovach, Petr | |
dc.contributor.author | Otachi, Yota | |
dc.contributor.author | van Leeuwen, Erik Jan | |
dc.date.accessioned | 2017-11-07T10:07:33Z | |
dc.date.available | 2017-11-07T10:07:33Z | |
dc.date.issued | 2012-09 | |
dc.Published | Bodlaender HL, Fomin V, Golovach P, Otachi Y, van Leeuwen EJ. Parameterized complexity of the spanning tree congestion problem. Algorithmica. 2012;64(1):85-111 | eng |
dc.identifier.issn | 0178-4617 | en_US |
dc.identifier.issn | 1432-0541 | en_US |
dc.identifier.uri | https://hdl.handle.net/1956/16868 | |
dc.description.abstract | We 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.language.iso | eng | eng |
dc.publisher | Springer | en_US |
dc.rights | Attribution CC BY-NC | eng |
dc.rights.uri | http://creativecommons.org/licenses/by-nc/3.0/ | eng |
dc.subject | Spanning tree congestion | eng |
dc.subject | Graph minor | eng |
dc.subject | Parameterized algorithms | eng |
dc.subject | Apex graph | eng |
dc.title | Parameterized complexity of the spanning tree congestion problem | en_US |
dc.type | Peer reviewed | |
dc.type | Journal article | |
dc.date.updated | 2017-09-28T09:27:16Z | |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2011 The Author(s) | en_US |
dc.identifier.doi | https://doi.org/10.1007/s00453-011-9565-7 | |
dc.identifier.cristin | 962551 | |
dc.source.journal | Algorithmica | |
dc.subject.nsi | VDP::Matematikk og naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Algoritmer og beregnbarhetsteori: 422 | |
dc.subject.nsi | VDP::Mathematics and natural scienses: 400::Information and communication science: 420::Algorithms and computability theory: 422 | |