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

DOI10.1007/978-3-030-42071-0_11MaRDI QIDQ5042455zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The computational complexity of some problems of linear algebra
• Reflections on multivariate algorithmics and problem parameterization
• On some fine-grained questions in algorithms and complexity
• Dynamic Programming and Fast Matrix Multiplication
• Matrix Rigidity from the Viewpoint of Parameterized Complexity

Cites work

• scientific article; zbMATH DE number 3573787 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
• Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication
• Color-coding
• Communication Complexity
• Competitive algorithms for generalized k-server in uniform metrics
• Compression via Matroids
• Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
• Counting Paths and Packings in Halves
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Mixing Color Coding-Related Techniques
• More applications of the polynomial method to algorithm design
• Narrow sieves for parameterized paths and packings
• Nondeterministic Quantum Query and Communication Complexities
• On maximum induced matchings in bipartite graphs
• On the ``log rank-conjecture in communication complexity
• Parameterized algorithms
• Probabilistic rank and matrix rigidity
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The polynomial method in circuit complexity applied to algorithm design (invited talk)
• Thirty-three miniatures. Mathematical and algorithmic applications of linear algebra

Cited in

(2)

• Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters
• A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5042455)