Fast parametrized algorithms for directed graph problems

• Applicant: Dr. Paul Bonsma
• Subject Area: Theoretical Computer Science
• Term: from 2009 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 121957638

• Final Report Year: 2011

Final Report Abstract

No abstract available

Publications

• Finding fullerene patches in polynomial time. In International Symposium on Algorithms and Computation 2009 (ISAAC 2009), volume 5878 of LNCS, pages 750–759. Springer, 2009
  P. Bonsma and F. Breuer
  
• Tight bounds and a fast FPT algorithm for directed max-leaf spanning tree. Accepted for ACM Transactions on Algorithms, 2009
  P. Bonsma and F. Dorn
  
• Counting hexagonal patches and independent sets in circle graphs. In 9th Latin American Theoretical Informatics Symposium (LATIN 2010), volume 6034 of LNCS, pages 603–614. Springer, 2010
  P. Bonsma and F. Breuer
  
• Max-leaves spanning tree is APX-hard for cubic graphs. Journal of Discrete Algorithms, 2010
  P. Bonsma
  
• Feedback vertex set in mixed graphs. Algorithms and Data Structures Symposium 2011 (WADS 2011)
  P. Bonsma and D. Lokshtanov