Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

DOI10.1007/978-3-030-42071-0_11OpenAlexW3019043336MaRDI QIDQ5042455

Jesper Nederlof

Publication date: 19 October 2022

Published in: Treewidth, Kernels, and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-42071-0_11

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On maximum induced matchings in bipartite graphs
• On the ``log rank-conjecture in communication complexity
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Narrow sieves for parameterized paths and packings
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Deterministic Truncation of Linear Matroids
• Mixing Color Coding-Related Techniques
• Counting Paths and Packings in Halves
• Color-coding
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
• Nondeterministic Quantum Query and Communication Complexities
• Communication Complexity
• Compression via Matroids
• Probabilistic rank and matrix rigidity
• Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
• Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication
• More Applications of the Polynomial Method to Algorithm Design
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms

This page was built for publication: Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices