Fine-grained complexity of coloring unit disks and balls
On planar graphs, many classic algorithmic problems enjoy a certain "square root phenomenon" and can be solved significantly faster than what is known to be possible on general graphs: for example, Independent Set, 3-Coloring, Hamiltonian Cycle, Dominating Set can be solved in time $2^{O(\sqrt{n})}...
Guardat en:
| Autors principals: | , , , , |
|---|---|
| Format: | Artigo |
| Idioma: | Inglês |
| Publicat: |
Carleton University
2018-10-01
|
| Col·lecció: | Journal of Computational Geometry |
| Accés en línia: | https://jocg.org/index.php/jocg/article/view/3064 |
| Etiquetes: |
Sense etiquetes, Sigues el primer a etiquetar aquest registre!
|