O(n) First-Order Queries on Graph Classes with Bounded Expansion
Date
2016
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Advisor
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Open Access
Terms of Use
Tripod URL
Identifier
Abstract
We collect the proofs and lemmas which enable linear time algorithms for first-order sentences on graph classes with bounded expansion. Bounded expansion is a property limiting the edge to vertex ratio of a graph and its minors by a function on the permitted amount of edge contraction. The linear runtime is achieved by evaluating quantifier-free first-order sentences on each node after a linear time preprocessing phase. We also demonstrate original linear time solutions developed for interesting non-trivial problems over certain bounded expansion graph classes. We conclude after discussing the implications and potential future applications of this line of research.