Faster Algebraic Algorithms for Path and Packing Problems
From MaRDI portal
Publication:3521948
DOI10.1007/978-3-540-70575-8_47zbMath1153.68562WikidataQ56639268 ScholiaQ56639268MaRDI QIDQ3521948
Publication date: 28 August 2008
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-70575-8_47
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Finding Detours is Fixed-Parameter Tractable, Kernelization of Graph Hamiltonicity: Proper $H$-Graphs, Unnamed Item, Going Far from Degeneracy, Approximate Counting of k-Paths: Deterministic and in Polynomial Space, Decomposition of Map Graphs with Applications., Shortest Two Disjoint Paths in Polynomial Time, Almost Optimal Cover-Free Families, Spotting Trees with Few Leaves, Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem, Unnamed Item, 1.61-approximation for min-power strong connectivity with two power levels, The \(k\)-distinct language: parameterized automata constructions, The Maximum Binary Tree Problem., Number of cycles of small length in a graph, Detours in directed graphs, Balanced substructures in bicolored graphs, Constrained multilinear detection and generalized graph motifs, An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs, Parameterized approximation algorithms for packing problems, On testing monomials in multivariate polynomials, Algebraic data retrieval algorithms for multi-channel wireless data broadcast, Matching and weighted \(P_2\)-packing: algorithms and kernels, On the parameterized complexity of the repetition free longest common subsequence problem, Faster algorithms for finding and counting subgraphs, Constrained multilinear detection for faster functional motif discovery, Detecting monomials with \(k\) distinct variables, Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs, Improved deterministic algorithms for weighted matching and packing problems, The minimum feasible tileset problem, Parameterized algorithms for list \(K\)-cycle, An improved kernelization algorithm for \(r\)-set packing, Fast exact algorithms using Hadamard product of polynomials, Finding paths of length \(k\) in \(O^{*}(2^k)\) time, Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem, An improved kernelization for \(P_{2}\)-packing, Clearing directed subgraphs by mobile agents. Variations on covering with paths, Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials, Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials, Algebraic methods in the congested clique, Partial information network queries, The maximum binary tree problem, Univariate ideal membership parameterized by rank, degree, and number of generators, A note on algebraic techniques for subgraph detection, Parameterized algorithms and kernels for almost induced matching, Algorithms for topology-free and alignment network queries, Faster deterministic parameterized algorithm for \(k\)-path, Finding, hitting and packing cycles in subexponential time on unit disk graphs, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, Monomials in arithmetic circuits: complete problems in the counting hierarchy, A fast parallel algorithm for minimum-cost small integral flows, Narrow sieves for parameterized paths and packings, A multivariate framework for weighted FPT algorithms, Space saving by dynamic algebraization based on tree-depth, Improved parameterized algorithms for network query problems, An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem, Nearly exact mining of frequent trees in large networks, Packing paths: recycling saves time, Randomized parameterized algorithms for the kidney exchange problem, Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms, A Selection of Lower Bounds for Arithmetic Circuits, TOWARD RANDOMIZED TESTING OF q-MONOMIALS IN MULTIVARIATE POLYNOMIALS, Parameterized Complexity and Subexponential-Time Computability, Improved Parameterized Algorithms for Network Query Problems, Almost Induced Matching: Linear Kernels and Parameterized Algorithms, Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets, Spotting Trees with Few Leaves, Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints, Mixing Color Coding-Related Techniques, A Problem Kernelization for Graph Packing