h1

% IMPORTANT: The following is UTF-8 encoded.  This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.

@PHDTHESIS{Reidl:565064,
      author       = {Reidl, Felix},
      othercontributors = {Rossmanith, Peter and Nešetril, Jarik},
      title        = {{S}tructural sparseness and complex networks},
      school       = {Aachen, Techn. Hochsch.},
      type         = {Dissertation},
      address      = {Aachen},
      publisher    = {Publikationsserver der RWTH Aachen University},
      reportid     = {RWTH-2015-07564},
      year         = {2016},
      note         = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
                      University 2016; Aachen, Techn. Hochsch., Diss., 2015},
      abstract     = {The field of complex networks has seen a steady growth in
                      the last decade, fuelled by an ever-growing collection of
                      relational data that ourlife in the information age
                      generates. While several structural commonalities of complex
                      networks have been observed - e.g. low density,heavily
                      skewed degree-distributions, or the small world property -
                      sofar no property has been discovered that is
                      algorithmically exploitableon a broad scale. Concurrently,
                      the theory of structurally sparse graphs has been
                      revolutionised by Robertson and Seymour’s graph minors
                      programme. Many tools and techniques, developed as
                      ‘by-products’ in the programme, have had a tremendous
                      impact on the research of parametrised and approximation
                      algorithms. They in particular enabled thedevelopment of
                      several algorithmic meta-theorems, that is, algorithmsthat
                      work for a large spectrum of problems on sparse inputs.In
                      this thesis, we work towards bringing the field of
                      structural sparsegraphs and the field of complex networks
                      closer together. We identifytwo notions of structural
                      sparseness based on the density of shallowminors as keys for
                      this endeavour: classes of bounded expansion andnowhere
                      dense classes as introduced by Nešetril and Ossona de
                      Mendez in their seminal work on a robust theory of
                      sparseness. In thefollowing, we demonstrate that these
                      sparse classes admit efficient algorithms for a huge number
                      of problems, some of which have applications in
                      domain-specific areas of network science. We further
                      provethat several fundamental network models exhibit these
                      properties anddemonstrate empirically that this also holds
                      true for a selection of real-world networks from various
                      domains. As a result, we can state that the theory of
                      structurally sparse graphsis applicable to complex networks
                      and, as a corollary, so is the richalgorithmic toolkit it
                      provides. This connection offers researchers fromboth the
                      field of algorithmic graph theory and network science
                      newapproaches, insights, and productive questions.},
      cin          = {121220 / 120000},
      ddc          = {004},
      cid          = {$I:(DE-82)121220_20140620$ / $I:(DE-82)120000_20140620$},
      typ          = {PUB:(DE-HGF)11},
      urn          = {urn:nbn:de:hbz:82-rwth-2015-075649},
      url          = {https://publications.rwth-aachen.de/record/565064},
}