@article{brown_moritz_michael p. o'brien_reidl_reiter_sullivan_2020, title={Exploring neighborhoods in large metagenome assembly graphs using spacegraphcats reveals hidden sequence diversity}, volume={21}, ISSN={["1474-760X"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85087661224&partnerID=MN8TOARS}, DOI={10.1186/s13059-020-02066-4}, abstractNote={AbstractGenomes computationally inferred from large metagenomic data sets are often incomplete and may be missing functionally important content and strain variation. We introduce an information retrieval system for large metagenomic data sets that exploits the sparsity of DNA assembly graphs to efficiently extract subgraphs surrounding an inferred genome. We apply this system to recover missing content from genome bins and show that substantial genomic sequence variation is present in a real metagenome. Our software implementation is available at https://github.com/spacegraphcats/spacegraphcatsunder the 3-Clause BSD License.}, number={1}, journal={GENOME BIOLOGY}, author={Brown, C. Titus and Moritz, Dominik and Michael P. O'Brien and Reidl, Felix and Reiter, Taylor and Sullivan, Blair D.}, year={2020}, month={Jul} } @article{reidl_villaamil_stavropoulos_2019, title={Characterising bounded expansion by neighbourhood complexity}, volume={75}, ISSN={["1095-9971"]}, DOI={10.1016/j.ejc.2018.08.001}, abstractNote={We show that a graph class G has bounded expansion if and only if it has bounded r-neighbourhood complexity, i.e. for any vertex set X of any subgraph H of G ∈ G, the number of subsets of X which are exact r-neighbourhoods of vertices of H on X is linear in the size of X.This is established by bounding the r-neighbourhood complexity of a graph in terms of both its r-centred colouring number and its weak r-colouring number, which provide known characterisations to the property of bounded expansion.}, journal={EUROPEAN JOURNAL OF COMBINATORICS}, author={Reidl, Felix and Villaamil, Fernando Sanchez and Stavropoulos, Konstantinos}, year={2019}, month={Jan}, pages={152–168} } @article{gutin_reidl_wahlstrom_2018, title={k-distinct in- and out-branchings in digraphs}, volume={95}, ISSN={["1090-2724"]}, DOI={10.1016/j.jcss.2018.01.003}, abstractNote={An out-branching and an in-branching of a digraph D are called k-distinct if each of them has k arcs absent in the other. Bang-Jensen, Saurabh and Simonsen (2016) proved that the problem of deciding whether a strongly connected digraph D has k-distinct out-branching and in-branching is fixed-parameter tractable (FPT) when parameterized by k. They asked whether the problem remains FPT when extended to arbitrary digraphs. Bang-Jensen and Yeo (2008) asked whether the same problem is FPT when the out-branching and in-branching have the same root. By linking the two problems with the problem of whether a digraph has an out-branching with at least k leaves (a leaf is a vertex of out-degree zero), we first solve the problem of Bang-Jensen and Yeo (2008). We then develop a new digraph decomposition and using it prove that the problem of Bang-Jensen et al. (2016) is FPT for all digraphs.}, journal={JOURNAL OF COMPUTER AND SYSTEM SCIENCES}, author={Gutin, Gregory and Reidl, Felix and Wahlstrom, Magnus}, year={2018}, month={Aug}, pages={86–97} } @inproceedings{chin_goodrich_o'brien_reidl_sullivan_poel_2016, title={Asymptotic analysis of equivalences and core-structures in Kronecker-style graph models}, DOI={10.1109/icdm.2016.0098}, abstractNote={Growing interest in modeling large, complexnetworks has spurred significant research into generative graphmodels. Kronecker-style models (e.g. SKG and R-MAT) are oftenused due to their scalability and ability to mimic key propertiesof real-world networks. Although a few papers theoreticallyestablish these models' behavior for specific parameters, manyclaims used to justify their use are supported only empirically. In this work, we prove several results using asymptotic analysiswhich illustrate that empirical studies may not fully capture thetrue behavior of the models. Paramount to the widespread adoption of Kronecker-stylemodels was the introduction of a linear-time edge-samplingvariant (R-MAT), which existing literature typically treats asinterchangeable with SKG. We prove that although several R-MAT formulations are asymptotically equivalent, their behaviordiverges from that of SKG. Further, we show these resultsare observable even at relatively small graph sizes. Second, weconsider a case where asymptotic analysis reveals unexpectedbehavior within a given model.}, booktitle={2016 ieee 16th international conference on data mining (icdm)}, author={Chin, A. J. and Goodrich, T. D. and O'Brien, M. P. and Reidl, F. and Sullivan, Blair D. and Poel, A.}, year={2016}, pages={829–834} }