LIPIcs.ICALP.2018.2.pdf
- Filesize: 160 kB
- 1 pages
Document
Sparsity - an Algorithmic Perspective (Invited Paper)
Author
-
Part of:
Volume:
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-07-04
Cite As Get BibTex
Jaroslav Nesetril. Sparsity - an Algorithmic Perspective (Invited Paper). In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.2
Abstract
It is a well known experience that for sparse structures one can find fast algorithm for some problems which seem to be otherwise complex. The recently developed theory of sparse classes of graphs (and structures) formalizes this. Particularly the dichotomy Nowhere vs Somewhere Dense presents a very robust tool to study and design algorithms and algorithmic metatheorems. This dichotomy can be characterized in many different ways leading tp broad applications. We survey some of the recent highlights. This is a joint work with Patrice Ossona de Mendez (EHESS Paris and Charles University Prague).
Subject Classification
ACM Subject Classification
- Theory of computation → Theory and algorithms for application domains
Keywords
- sparse structures
- algorithm design
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads