Fast Parameterized Preprocessing for Polynomial-Time Solvable Graph Problems

2024/03/25 by Anne-Sophie Himmel, George B. Mertzios, André Nichterlein +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Interconnection Networks and Systems

paper · pdf · doi:10.1145/3624713

Abstract

The challenge of transforming polynomial-time algorithms to really efficient ones.

Related

• Preprocessing Complexity for Some Graph Problems Parameterized by Structural Parameters
• Fast Parallel Fixed-Parameter Algorithms via Color Coding
• Parameter Selection and Pre-Conditioning for a Graph Form Solver
• Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems
• Limits of Preprocessing