Divide-and-Color

DOI10.1007/11917496_6MaRDI QIDQ3522942zbMATH OpenOpenAlexFDO

Authors Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith

Publication date 4 September 2008

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11917496_6

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Color-coding
• Improved algorithms for path, matching, and packing problems
• Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract)
• scientific article; zbMATH DE number 7368393
• Randomized divide-and-conquer: improved path, matching, and packing algorithms

Cited in

(30)

• The parameterized complexity of the induced matching problem
• On problems without polynomial kernels
• Improved parameterized set splitting algorithms: A Probabilistic approach
• A note on algebraic techniques for subgraph detection
• Faster deterministic parameterized algorithm for k-path
• Narrow sieves for parameterized paths and packings
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Sharp separation and applications to exact and parameterized algorithms
• An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem
• Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract)
• Kernel bounds for path and cycle problems
• Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters
• A Problem Kernelization for Graph Packing
• Kernel bounds for path and cycle problems
• Color-coding
• Faster algorithms for finding and counting subgraphs
• Parameterized complexity of induced graph matching on claw-free graphs
• Finding detours is fixed-parameter tractable
• Going far from degeneracy
• Going far from degeneracy
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
• Finding monotone paths in edge-ordered graphs
• Detours in directed graphs
• Methods for finding paths of a prescribed length in weighted graphs
• Parameterized complexity of feedback vertex set with connectivity constraints
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Efficient algorithms for clique problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time

This page was built for publication: Divide-and-Color

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