License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.2
URN: urn:nbn:de:0030-drops-90062
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9006/
Go to the corresponding LIPIcs Volume Portal

Nesetril, Jaroslav

Sparsity - an Algorithmic Perspective (Invited Paper)

pdf-format:
LIPIcs-ICALP-2018-2.pdf (0.2 MB)

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).

BibTeX - Entry

@InProceedings{nesetril:LIPIcs:2018:9006,
  author =	{Jaroslav Nesetril},
  title =	{{Sparsity - an Algorithmic Perspective (Invited Paper)}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9006},
  URN =		{urn:nbn:de:0030-drops-90062},
  doi =		{10.4230/LIPIcs.ICALP.2018.2},
  annote =	{Keywords: sparse structures, algorithm design}
}

Keywords: sparse structures, algorithm design
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI