CS614. Advanced Algorithms. Exam 2.

CS614. Advanced Algorithms.

Exam 2

Back to the course page

List of Papers

  1. Arturo I. Merino, Torsten Mütze, Aaron Williams: All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges. FUN 2022: 22:1-22:28 [PDF]

  2. Daniel Lokshtanov, Bernardo Subercaseaux: Wordle Is NP-Hard. FUN 2022: 19:1-19:8 [PDF]

  3. Christoph Brause, Ingo Schiermeyer: Kernelization of the 3-path vertex cover problem. Discret. Math. 339(7): 1935-1939 (2016) [PDF]

  4. Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi: Parameterized Complexity of Safe Set. J. Graph Algorithms Appl. 24(3): 215-245 (2020) [PDF]

Focus on Sections 5 and 7 for the presentation.

  1. Radovan Cervený, Ondrej Suchý: Faster FPT Algorithm for 5-Path Vertex Cover. MFCS 2019: 32:1-32:13 [PDF]

Since there are several cases to the branching algorithm, there is no need to comprehensively cover them in the presentation

  1. Fedor V. Fomin, Torstein J. F. Strømme: Vertex Cover Structural Parameterization Revisited. WG 2016: 171-182 [PDF]

Focus on Section 3 for the presentation.

  1. A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation. SOSA 2019: 15:1-15:21 [PDF]

Choose an appropriate subset of results to present.

  1. Dan Hefetz, Orna Kupferman, Amir Lellouche, Gal Vardi: Spanning-Tree Games. MFCS 2018: 35:1-35:16 [PDF]

  2. Michael Lampis, Valia Mitsou: The Computational Complexity of the Game of Set and Its Theoretical Applications. LATIN 2014: 24-34 [PDF]

Focus on the NP-completeness and FPT results here.

  1. Julián Mestre: A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses. APPROX-RANDOM 2005: 182-191 [PDF]

© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

A problem worthy of attack proves its worth by fighting back.

Paul Erdos