Color-coding

DOI10.1145/195058.195179zbMath1344.68092OpenAlexW1980069488MaRDI QIDQ2817625

Raphy Yuster, Uri Zwick, Noga Alon

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195179

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

The Birth and Early Years of Parameterized Complexity ⋮ A Basic Parameterized Complexity Primer ⋮ The existence of homeomorphic subgraphs in chordal graphs ⋮ Complexity of searching an immobile hider in a graph ⋮ Algorithms for long paths in graphs ⋮ Almost optimal query algorithm for hitting set using a subset query ⋮ On the approximability of some degree-constrained subgraph problems ⋮ Finding even cycles even faster ⋮ Understanding planning with incomplete information and sensing ⋮ Main-memory triangle computations for very large (sparse (power-law)) graphs ⋮ Algorithm for two disjoint long paths in 2-connected graphs ⋮ An ILP formulation and genetic algorithm for the maximum degree-bounded connected subgraph problem ⋮ Unnamed Item ⋮ Degree-Constrained Subgraph Problems: Hardness and Approximation Results