Florian Zickfeld Dissertation

  • 1.

    Bonsma, P.: Spanning trees with many leaves in graphs with minimum degree three. SIAM J. Discrete Math. 22(3), 920–937 (2008)MathSciNetCrossRefMATHGoogle Scholar

  • 2.

    Bonsma, P., Zickfeld, F.: Spanning trees with many leaves in graphs without diamonds and blossoms. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 531–543. Springer, Heidelberg (2008)CrossRefGoogle Scholar

  • 3.

    Cheng, X., Huang, X., Li, D., Wu, W., Du, D.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 42(4), 202–208 (2003)MathSciNetCrossRefMATHGoogle Scholar

  • 4.

    Correa, J.R., Fernandes, C.G., Matamala, M., Wakabayashi, Y.: A 5/3-approximation for finding spanning trees with many leaves in cubic graphs. In: Kaklamanis, C., Skutella, M. (eds.) WAOA 2007. LNCS, vol. 4927, pp. 184–192. Springer, Heidelberg (2008)CrossRefGoogle Scholar

  • 5.

    Diestel, R.: Graph Theory. Springer, New York (1997)MATHGoogle Scholar

  • 6.

    Drescher, M., Vetta, A.: An approximation algorithm for the max leaf spanning arborescence problem. ACM transactions on algorithms (to appear)Google Scholar

  • 7.

    Estivill-Castro, V., Fellows, M.R., Langston, M.A., Rosamond, F.A.: FPT is P-time extremal structure I. In: ACiD 2005. Texts in algorithmics, vol. 4, pp. 1–41. King’s College Publications (2005)Google Scholar

  • 8.

    Fomin, F.V., Grandoni, F., Kratsch, D.: Solving connected dominating set faster than \(2\sp n\). In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol. 4337, pp. 152–163. Springer, Heidelberg (2006)CrossRefGoogle Scholar

  • 9.

    Galbiati, G., Morzenti, A., Maffioli, F.: On the approximability of some maximum spanning tree problems. Theoret. Comput. Sci. 181(1), 107–118 (1997)MathSciNetCrossRefMATHGoogle Scholar

  • 10.

    Griggs, J.R., Kleitman, D.J., Shastri, A.: Spanning trees with many leaves in cubic graphs. J. Graph Theory 13(6), 669–695 (1989)MathSciNetCrossRefMATHGoogle Scholar

  • 11.

    Griggs, J.R., Wu, M.: Spanning trees in graphs of minimum degree 4 or 5. Discrete Math. 104(2), 167–183 (1992)MathSciNetCrossRefMATHGoogle Scholar

  • 12.

    Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374–387 (1998)MathSciNetCrossRefMATHGoogle Scholar

  • 13.

    Kleitman, D.J., West, D.B.: Spanning trees with many leaves. SIAM J. Discrete Math. 4(1), 99–106 (1991)MathSciNetCrossRefMATHGoogle Scholar

  • 14.

    Lemke, P.: The maximum-leaf spanning tree problem in cubic graphs is NP-complete. IMA publication no. 428, University of Minnesota, Mineapolis (1988)Google Scholar

  • 15.

    Loryś, K., Zwoźniak, G.: Approximation algorithm for the maximum leaf spanning tree problem for cubic graphs. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 686–697. Springer, Heidelberg (2002)CrossRefGoogle Scholar

  • 16.

    Lu, H., Ravi, R.: Approximating maximum leaf spanning trees in almost linear time. Journal of Algorithms 29(1), 132–141 (1998)MathSciNetCrossRefMATHGoogle Scholar

  • 17.

    Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.: A greedy approximation for minimum connected dominating sets. Theoret. Comput. Sci. 329(1-3), 325–330 (2004)MathSciNetCrossRefMATHGoogle Scholar

  • 18.

    Solis-Oba, R.: 2-approximation algorithm for finding a spanning tree with maximum number of leaves. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol. 1461, pp. 441–452. Springer, Heidelberg (1998)Google Scholar

  • 19.

    Zickfeld, F.: Geometric and combinatorial structures on graphs. PhD thesis, Technische Universität Berlin, Berlin (2007)Google Scholar

  • 1.

    Bodlaender, H.L.: On linear time minor tests with depth-first search. J. Algorithms 14(1), 1–23 (1993)MATHCrossRefMathSciNetGoogle Scholar

  • 2.

    Bonsma, P.S.: Sparse cuts, matching-cuts and leafy trees in graphs. PhD thesis, University of Twente, Enschede, the Netherlands (2006), http://purl.org/utwente/57117

  • 3.

    Bonsma, P.S., Brueggemann, T., Woeginger, G.J.: A faster FPT algorithm for finding spanning trees with many leaves. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 259–268. Springer, Heidelberg (2003)Google Scholar

  • 4.

    Correa, J.R., Fernandes, C.G., Matamala, M., Wakabayashi, Y.: A 5/3-approximation for finding spanning trees with many leaves in cubic graphs. In: WAOA 2007 (to appear, 2007)Google Scholar

  • 5.

    Estivill-Castro, V., Fellows, M.R., Langston, M.A., Rosamond, F.A.: FPT is P-time extremal structure I. In: ACiD 2005. Texts in algorithmics, vol. 4, pp. 1–41. King’s College PublicationsGoogle Scholar

  • 6.

    Flum, J., Grohe, M.: Parameterized complexity theory. Springer, Berlin (2006)Google Scholar

  • 7.

    Griggs, J.R., Kleitman, D.J., Shastri, A.: Spanning trees with many leaves in cubic graphs. J. Graph Theory 13(6), 669–695 (1989)MATHCrossRefMathSciNetGoogle Scholar

  • 8.

    Kleitman, D.J., West, D.B.: Spanning trees with many leaves. SIAM J. Discrete Math. 4(1), 99–106 (1991)MATHCrossRefMathSciNetGoogle Scholar

  • 9.

    Solis-Oba, R.: 2-approximation algorithm for finding a spanning tree with maximum number of leaves. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol. 1461, pp. 441–452. Springer, Heidelberg (1998)CrossRefGoogle Scholar

  • 0 thoughts on “Florian Zickfeld Dissertation”

      -->

    Leave a Comment

    Your email address will not be published. Required fields are marked *