On the Locality of Some NP-Complete Problems

DOI10.1007/978-3-642-31585-5_37zbMath1369.68215arXiv1204.6675OpenAlexW2169324896MaRDI QIDQ3167029

Leonid Barenboim

Publication date: 1 November 2012

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.6675

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (7)

A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Distributed strong diameter network decomposition ⋮ Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Computing large independent sets in a single round ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs

This page was built for publication: On the Locality of Some NP-Complete Problems