Algorithms for Classes of Graphs with Bounded Expansion

DVORAK, Z and Daniel KRÁĽ. Algorithms for Classes of Graphs with Bounded Expansion. GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE. BERLIN: SPRINGER-VERLAG BERLIN, 2010, vol. 5911, p. 17-32. ISSN 0302-9743.

Basic information

Original name

Algorithms for Classes of Graphs with Bounded Expansion

Authors

DVORAK, Z and Daniel KRÁĽ

Edition

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, BERLIN, SPRINGER-VERLAG BERLIN, 2010, 0302-9743

---

Other information

Language

English

Type of outcome

Article in a journal

Confidentiality degree

is not subject to a state or trade secret

UT WoS

000278979300002

---

Abstract

In the original language

We overview algorithmic results for classes of sparse graphs emphasizing new developments in this area. We focus on recently introduced classes of graphs with bounded expansion and nowhere-dense graphs and relate algorithmic meta-theorems for these classes or graphs to their analogues for proper minor-closed classes of graphs, classes of graphs with bounded tree-width, locally bounded tree-width and locally excluding a minor.