Divide-and-Color

DOI10.1007/11917496_6zbMath1167.68411OpenAlexW1812837484MaRDI QIDQ3522942

Daniel Mölle, Joachim Kneis, 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 theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (27)

A note on algebraic techniques for subgraph detection ⋮ Kernel Bounds for Path and Cycle Problems ⋮ Narrow sieves for parameterized paths and packings ⋮ Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Finding monotone paths in edge-ordered graphs ⋮ Kernel bounds for path and cycle problems ⋮ Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters ⋮ Detours in directed graphs ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem ⋮ Faster algorithms for finding and counting subgraphs ⋮ Going Far from Degeneracy ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Algorithm engineering for color-coding with applications to signaling pathway detection ⋮ Faster fixed-parameter tractable algorithms for matching and packing problems ⋮ Unnamed Item ⋮ Efficient algorithms for clique problems ⋮ Finding paths of length \(k\) in \(O^{*}(2^k)\) time ⋮ Faster deterministic parameterized algorithm for \(k\)-path ⋮ A Problem Kernelization for Graph Packing ⋮ On the complexity of finding internally vertex-disjoint long directed paths ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ The parameterized complexity of the induced matching problem ⋮ On problems without polynomial kernels ⋮ Improved parameterized set splitting algorithms: A Probabilistic approach ⋮ Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs

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