Skip to main content Accessibility help
×
  1. Home
  2. Books
  3. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
    Show more authors
    • You may already have access via personal or institutional login
  • Select format
  • Publisher:
    Cambridge University Press
    Publication date:
    30 August 2017
    17 August 2017
    ISBN:
    9781139028868
    9781107014527
    DOI:
    https://doi.org/10.1017/9781139028868
    Dimensions:
    (228 x 152 mm)
    Weight & Pages:
    0.88kg, 554 Pages
    Dimensions:
    Weight & Pages:
    • Subjects:
    Mathematics, Algorithmics, Complexity, Computer Algebra, Computational Geometry, Logic, Categories and Sets, Computer Science, Programming Languages and Applied Logic
    Series:
    Lecture Notes in Logic (47)
You may already have access via personal or institutional login
    • Selected: Digital
    Add to cart View cart Buy from Cambridge.org
    Subjects:
    Mathematics, Algorithmics, Complexity, Computer Algebra, Computational Geometry, Logic, Categories and Sets, Computer Science, Programming Languages and Applied Logic
    Series:
    Lecture Notes in Logic (47)
    Information

    Book description

    Descriptive complexity theory establishes a connection between the computational complexity of algorithmic problems (the computational resources required to solve the problems) and their descriptive complexity (the language resources required to describe the problems). This groundbreaking book approaches descriptive complexity from the angle of modern structural graph theory, specifically graph minor theory. It develops a 'definable structure theory' concerned with the logical definability of graph theoretic concepts such as tree decompositions and embeddings. The first part starts with an introduction to the background, from logic, complexity, and graph theory, and develops the theory up to first applications in descriptive complexity theory and graph isomorphism testing. It may serve as the basis for a graduate-level course. The second part is more advanced and mainly devoted to the proof of a single, previously unpublished theorem: properties of graphs with excluded minors are decidable in polynomial time if, and only if, they are definable in fixed-point logic with counting.

    Reviews

    'The book is divided evenly into two parts. Part I gives background and definitions of the main notions, and makes the book self-contained. Many results from descriptive complexity theory, and the author’s earlier results, are clearly presented. Part II is devoted to the main theorem about graphs with excluded minors. The book ends with a symbol index and an index.'

    Pascal Michel Source: Mathematical Reviews

    Refine List

    Actions for selected content:

    Select all | Deselect all
    • View selected items
    • Export citations
    • Download PDF (zip)
    • Save to Kindle
    • Save to Dropbox
    • Save to Google Drive

    Save Search

    You can save your searches here and later view and run them again in "My saved searches".

    Please provide a title, maximum of 40 characters.
    Cancel
    ×

    Contents

    Contents

    Metrics

    Altmetric attention score

    Full text views

    Total number of HTML views: 0
    Total number of PDF views: 0 *
    Loading metrics...

    Book summary page views

    Total views: 0 *
    Loading metrics...

    * Views captured on Cambridge Core between #date#. This data will be updated every 24 hours.

    Usage data cannot currently be displayed.

    Accessibility standard: Unknown

    Why this information is here

    This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.

    Accessibility Information

    Accessibility compliance for the PDF of this book is currently unknown and may be updated in the future.