Abstract
The k-Internal Out-Branching (k-IOB) problem asks if a given directed graph has an out-branching (i.e., a spanning tree with exactly one node of in-degree 0) with at least k internal nodes. The k-Internal Spanning Tree (k-IST) problem is a special case of k-IOB, which asks if a given undirected graph has a spanning tree with at least k internal nodes. We present an O *(4k) time randomized algorithm for k-IOB, which improves the O * running times of the best known algorithms for both k-IOB and k-IST. Moreover, for graphs of bounded degree Δ, we present an \(O^*(2^{(2-\frac{\Delta+1}{\Delta(\Delta-1)})k})\) time randomized algorithm for k-IOB. Both our algorithms use polynomial space.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Cohen, N., Fomin, F.V., Gutin, G., Kim, E.J., Saurabh, S., Yeo, A.: Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. J. Comput. Syst. Sci. 76(7), 650–662 (2010)
Demers, A., Downing, A.: Minimum leaf spanning tree. US Patent no. 6,105,018 (August 2013)
Fomin, F.V., Gaspers, S., Saurabh, S., Thomassé, S.: A linear vertex kernel for maximum internal spanning tree. J. Comput. Syst. Sci. 79(1), 1–6 (2013)
Fomin, F.V., Grandoni, F., Lokshtanov, D., Saurabh, S.: Sharp separation and applications to exact and parameterized algorithms. Algorithmica 63(3), 692–706 (2012)
Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: Proc. STOC, pp. 47–63 (1974)
Gutin, G., Razgon, I., Kim, E.J.: Minimum leaf out-branching and related problems. Theor. Comput. Sci. 410(45), 4571–4579 (2009)
Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 575–586. Springer, Heidelberg (2008)
Koutis, I., Williams, R.: Limits and applications of group algebras for parameterized problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 653–664. Springer, Heidelberg (2009)
Nederlof, J.: Fast polynomial-space algorithms using mobius inversion: improving on steiner tree and related problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 713–725. Springer, Heidelberg (2009)
Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford University Press (2006)
Ozeki, K., Yamashita, T.: Spanning trees: A survey. Graphs and Combinatorics 27(1), 1–26 (2011)
Prieto, E., Sloper, C.: Reducing to independent set structure – the case of k-internal spanning tree. Nord. J. Comput. 12(3), 308–318 (2005)
Rédei, L.: Ein kombinatorischer satz. Acta Litteraria Szeged 7, 39–43 (1934)
Raible, D., Fernau, H., Gaspers, D., Liedloff, M.: Exact and parameterized algorithms for max internal spanning tree. Algorithmica 65(1), 95–128 (2013)
Salamon, G.: A survey on algorithms for the maximum internal spanning tree and related problems. Electronic Notes in Discrete Mathematics 36, 1209–1216 (2010)
Skulrattanakulchai, S.: Delta-list vertex coloring in linear time. Inf. Process. Lett. 98(3), 101–106 (2006)
Williams, R.: Finding paths of length k in O *(2k) time. Inf. Process. Lett. 109(6), 315–318 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Zehavi, M. (2013). Algorithms for k-Internal Out-Branching. In: Gutin, G., Szeider, S. (eds) Parameterized and Exact Computation. IPEC 2013. Lecture Notes in Computer Science, vol 8246. Springer, Cham. https://doi.org/10.1007/978-3-319-03898-8_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-03898-8_30
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03897-1
Online ISBN: 978-3-319-03898-8
eBook Packages: Computer ScienceComputer Science (R0)