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

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

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

(28)

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

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)