Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Testing first-order properties for subclasses of sparse graphs

Tools
- Tools
+ Tools

Dvořák, Zdeněk, Králʼ, Daniel and Thomas, Robin (2013) Testing first-order properties for subclasses of sparse graphs. Journal of the ACM, Volume 60 (Number 5). Article number 36. doi:10.1145/2499483

[img]
Preview
Text
WRAP_Kral_1173667-ma-060613-databe.pdf - Accepted Version

Download (635Kb) | Preview
Official URL: http://dx.doi.org/10.1145/2499483

Request Changes to record.

Abstract

We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Nešetřil and Ossona de Mendez. This generalizes several results from the literature, because many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no subgraph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We deduce that there is an almost linear-time algorithm for deciding FO properties in classes of graphs with locally bounded expansion.

More generally, we design a dynamic data structure for graphs belonging to a fixed class of graphs of bounded expansion. After a linear-time initialization the data structure allows us to test an FO property in constant time, and the data structure can be updated in constant time after addition/deletion of an edge, provided the list of possible edges to be added is known in advance and their simultaneous addition results in a graph in the class. All our results also hold for relational structures and are based on the seminal result of Nešetřil and Ossona de Mendez on the existence of low tree-depth colorings.

Item Type: Journal Article
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH): Algorithms, Graph theory
Journal or Publication Title: Journal of the ACM
Publisher: Association for Computing Machinery, Inc.
ISSN: 0004-5411
Official Date: October 2013
Dates:
DateEvent
October 2013Published
Volume: Volume 60
Number: Number 5
Page Range: Article number 36
DOI: 10.1145/2499483
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us