Minimum Leaf Out-branching and Related Problems

H. Alt, N. Blum, K. Melhorn, and M. Paul, Computing of maximum cardinality matching in a bipartite graph in time O ⁡ ( n 1.5 ​ m / log ⁡ n ) O(n^{1.5}\sqrt{m/\log n}) . Inf. Proc. Letters

1991

Earlier work this paper cites.

R.G. Downey and M.R. Fellows, Parameterized Complexity

1999

Earlier work this paper cites.

M. Mahajan and V. Raman, Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms

1999

Earlier work this paper cites.

J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications

2000

Earlier work this paper cites.

A. Demers and A. Downing, Minimum leaf spanning tree. US Patent no. 6,105,018, August 2000

2000

Earlier work this paper cites.

E. Prieto and C. Sloper, Either/Or: Using Vertex Cover Structure in desigining FPT-algorithms - The Case of k k -Internal Spanning Tree, Proc. WADS’2003

2003

Earlier work this paper cites.

B. Chor, M. Fellows and D. Juedes, Linear Kernels in Linear Time, or How to Save k Colors in O ⁡ ( n 2 ) O(n^{2}) steps. Proc. WG’2004

2004

Cited alongside, same era.

M. Fellows, P. Heggernes, F. Rosamond, C. Sloper and J.A. Telle, Finding k k -disjoint triangles in an arbitrary graph. Proc. WG’2004

2004

Cited alongside, same era.

H. Fernau, Parameterized Algorithmics: A Graph-theoretic Approach

2005

Cited alongside, same era.

H. Fernau, Parameterized Algorithmics for Linear Arrangement Problems. Manscript, July 2005

2005

Cited alongside, same era.

E. Prieto and C. Sloper, Reducing To Independent Set Structure - The Case of k k -Internal Spanning Tree, Nordic Journal of Computing

Original

2005

Cited alongside, same era.

R. Niedermeier. Invitation to Fixed-Parameter Algorithms

2006

Later among the works it cites.

H.L. Bodlaender, R.G. Downey, M.R. Fellows and D. Hermelin, On problems without polynomial kernels. Technical report UU-CS-2007-046 (2007), Utrecht University

2007

Later among the works it cites.

J. Guo and R. Niedermeier, Invitation to Data Reduction and Problem Kernelization. ACM SIGACT News

2007

Later among the works it cites.

G. Gutin, A. Rafiey, S. Szeider and A. Yeo, The Linear Arrangement Problem Parameterized Above Guaranteed Value. Theory of Computing Systems

2007

Later among the works it cites.

P. Heggernes, C. Paul, J.A. Telle, and Y. Villanger, Interval completion with few edges. Proc. STOC 2007 - 39th ACM Symposium on Theory of Computing, 374 – 381

2007

Later among the works it cites.