Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
From MaRDI portal
Publication:3654388
DOI10.1137/080716475zbMath1191.68849OpenAlexW2092088134MaRDI QIDQ3654388
Joachim Kneis, Sing-Hoi Sze, Daniel Mölle, Songjian Lu, Fenghui Zhang, Stefan Richter, Jian'er Chen, Peter Rossmanith
Publication date: 6 January 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1969.1/178675
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Randomized algorithms (68W20)
Related Items
Spotting Trees with Few Leaves, Assigning channels via the meet-in-the-middle approach, Spotting Trees with Few Leaves, Parameterized and approximation algorithms for finding two disjoint matchings, Edge-disjoint packing of stars and cycles, Mixing Color Coding-Related Techniques, Parameterized approximation algorithms for packing problems, Parameterized Complexity and Subexponential-Time Computability, Parameterized algorithms for edge biclique and related problems, Edge-Disjoint Packing of Stars and Cycles, The parameterized complexity of unique coverage and its variants, Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets, Narrow sieves for parameterized paths and packings, QUBO formulations of the longest path problem, Improved Parameterized Algorithms for Network Query Problems, Improved parameterized algorithms for network query problems, Detours in directed graphs, Parameterized Counting and Cayley Graph Expanders, Contracting graphs to paths and trees, Digraph width measures in parameterized algorithmics, Going Far from Degeneracy, Parameterized algorithms for list \(K\)-cycle, Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials, Improved deterministic algorithms for weighted matching and packing problems, A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families, Unnamed Item, Partial information network queries, Parameterized complexity of \textsc{maximum edge colorable subgraph}, Faster deterministic parameterized algorithm for \(k\)-path, Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem, The \(k\)-distinct language: parameterized automata constructions, Long directed \((s,t)\)-path: FPT algorithm, Finding Detours is Fixed-Parameter Tractable, Approximate Counting of k-Paths: Deterministic and in Polynomial Space, On Digraph Width Measures in Parameterized Algorithmics, Parameterized complexity of maximum edge colorable subgraph, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
