Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Subgraphs satisfying MSO properties on z-topologically orderable digraphs
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2013 (English)In: Parameterized and Exact Computation: 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, Springer, 2013, 123-136 p.Conference paper, Published paper (Refereed)
Abstract [en]

We introduce the notion of z-topological orderings for digraphs. We prove that given a digraph G on n vertices admitting a z-topological ordering, together with such an ordering, one may count the number of subgraphs of G that at the same time satisfy a monadic second order formula φ and are the union of k directed paths, in time f(φ,k,z)·nO(k·z). Our result implies the polynomial time solvability of many natural counting problems on digraphs admitting z-topological orderings for constant values of z and k. Concerning the relationship between z-topological orderability and other digraph width measures, we observe that any digraph of directed path-width d has a z-topological ordering for z ≤ 2d + 1. On the other hand, there are digraphs on n vertices admitting a z-topological order for z = 2, but whose directed path-width is Θ(log n). Since graphs of bounded directed path-width can have both arbitrarily large undirected tree-width and arbitrarily large clique width, our result provides for the first time a suitable way of partially transposing metatheorems developed in the context of the monadic second order logic of graphs of constant undirected tree-width and constant clique width to the realm of digraph width measures that are closed under taking subgraphs and whose constant levels incorporate families of graphs of arbitrarily large undirected tree-width and arbitrarily large clique width.

Place, publisher, year, edition, pages
Springer, 2013. 123-136 p.
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 8246 LNCS
Keyword [en]
Algorithmic Meta-theorems, Digraph Width Measures, Monadic Second Order Logic of Graphs, Slice Theory
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-143599DOI: 10.1007/978-3-319-03898-8_12Scopus ID: 2-s2.0-84893064211ISBN: 978-331903897-1 (print)OAI: oai:DiVA.org:kth-143599DiVA: diva2:707783
Conference
8th International Symposium on Parameterized and Exact Computation, IPEC 2013; Sophia Antipolis; France; 4 September 2013 through 6 September 2013
Note

QC 20140325

Available from: 2014-03-25 Created: 2014-03-25 Last updated: 2014-03-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
De Oliveira Oliveira, Mateus
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 34 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf