On the Complexity of Frequent Subtree Mining in Very Simple Structures.

LANCASTER UNIVERSITY LEIPZIG

Text available via DOI:

https://doi.org/10.1007/978-3-319-23708-4_14
Final published version

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Published

Standard

On the Complexity of Frequent Subtree Mining in Very Simple Structures. / Welke, Pascal; Horváth, Tamás; Wrobel, Stefan.
Springer Switerzland. Vol. 9046 Springer Nature, 2015. p. 194-209 (Lecture Notes in Computer Science; Vol. 9046).

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Harvard

Welke, P, Horváth, T & Wrobel, S 2015, On the Complexity of Frequent Subtree Mining in Very Simple Structures. in Springer Switerzland. vol. 9046, Lecture Notes in Computer Science, vol. 9046, Springer Nature, pp. 194-209, 24th International Conference on Inductive Logic Programming , Nancy, 14/09/14. https://doi.org/10.1007/978-3-319-23708-4_14

APA

Welke, P., Horváth, T., & Wrobel, S. (2015). On the Complexity of Frequent Subtree Mining in Very Simple Structures. In Springer Switerzland (Vol. 9046, pp. 194-209). (Lecture Notes in Computer Science; Vol. 9046). Springer Nature. https://doi.org/10.1007/978-3-319-23708-4_14

Vancouver

Welke P, Horváth T, Wrobel S. On the Complexity of Frequent Subtree Mining in Very Simple Structures. In Springer Switerzland. Vol. 9046. Springer Nature. 2015. p. 194-209. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-23708-4_14

Author

Welke, Pascal ; Horváth, Tamás ; Wrobel, Stefan. / On the Complexity of Frequent Subtree Mining in Very Simple Structures. Springer Switerzland. Vol. 9046 Springer Nature, 2015. pp. 194-209 (Lecture Notes in Computer Science).

Bibtex

@inproceedings{91e81b0978dd4fcfb193062723142823,

title = "On the Complexity of Frequent Subtree Mining in Very Simple Structures.",

abstract = "We study the complexity of frequent subtree mining in very simple graphs beyond forests. We show for d-tenuous outerplanar graphs that frequent subtrees can be listed with polynomial delay if the cycle degree, i.e., the maximum number of blocks that share a common vertex, is bounded by some constant. The crucial step in the proof of this positive result is a polynomial time algorithm deciding subgraph isomorphism from trees into d-tenuous outerplanar graphs of bounded cycle degree. We obtain this algorithm by generalizing the algorithm of Shamir and Tsur that decides subgraph isomorphism between trees. Our results may also be of some interest to algorithmic graph theory, as they indicate that even for very simple structures, the cycle degree is a crucial parameter for the tractability of subgraph isomorphism. We also discuss some interesting problems towards generalizing the positive result of this work.",

author = "Pascal Welke and Tam{\'a}s Horv{\'a}th and Stefan Wrobel",

note = "DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.; 24th International Conference on Inductive Logic Programming ; Conference date: 14-09-2014 Through 16-09-2014",

year = "2015",

month = dec,

day = "27",

doi = "10.1007/978-3-319-23708-4_14",

language = "Undefined/Unknown",

isbn = "978-3-319-23707-7",

volume = "9046",

series = "Lecture Notes in Computer Science",

publisher = "Springer Nature",

pages = "194--209",

booktitle = "Springer Switerzland",

}

RIS

TY - GEN

T1 - On the Complexity of Frequent Subtree Mining in Very Simple Structures.

AU - Welke, Pascal

AU - Horváth, Tamás

AU - Wrobel, Stefan

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2015/12/27

Y1 - 2015/12/27

N2 - We study the complexity of frequent subtree mining in very simple graphs beyond forests. We show for d-tenuous outerplanar graphs that frequent subtrees can be listed with polynomial delay if the cycle degree, i.e., the maximum number of blocks that share a common vertex, is bounded by some constant. The crucial step in the proof of this positive result is a polynomial time algorithm deciding subgraph isomorphism from trees into d-tenuous outerplanar graphs of bounded cycle degree. We obtain this algorithm by generalizing the algorithm of Shamir and Tsur that decides subgraph isomorphism between trees. Our results may also be of some interest to algorithmic graph theory, as they indicate that even for very simple structures, the cycle degree is a crucial parameter for the tractability of subgraph isomorphism. We also discuss some interesting problems towards generalizing the positive result of this work.

AB - We study the complexity of frequent subtree mining in very simple graphs beyond forests. We show for d-tenuous outerplanar graphs that frequent subtrees can be listed with polynomial delay if the cycle degree, i.e., the maximum number of blocks that share a common vertex, is bounded by some constant. The crucial step in the proof of this positive result is a polynomial time algorithm deciding subgraph isomorphism from trees into d-tenuous outerplanar graphs of bounded cycle degree. We obtain this algorithm by generalizing the algorithm of Shamir and Tsur that decides subgraph isomorphism between trees. Our results may also be of some interest to algorithmic graph theory, as they indicate that even for very simple structures, the cycle degree is a crucial parameter for the tractability of subgraph isomorphism. We also discuss some interesting problems towards generalizing the positive result of this work.

U2 - 10.1007/978-3-319-23708-4_14

DO - 10.1007/978-3-319-23708-4_14

M3 - Conference contribution/Paper

SN - 978-3-319-23707-7

VL - 9046

T3 - Lecture Notes in Computer Science

SP - 194

EP - 209

BT - Springer Switerzland

PB - Springer Nature

T2 - 24th International Conference on Inductive Logic Programming

Y2 - 14 September 2014 through 16 September 2014

ER -

Research

Links

Text available via DOI: