0. This graph is a counterexample to a conjecture of Benzi (2014) [1, Conjecture 3.1]. We also show that there exist infinitely many temperatures β0>0 so that SV(G,β0)=lognG if and only if a graph G is walk-regular.}, journal={Linear Algebra and its Applications}, publisher={Elsevier BV}, author={Kloster, Kyle and Král', Daniel and Sullivan, Blair D.}, year={2018}, month={Jun}, pages={115–121} } @inproceedings{sullivan_van der poel_2017, title={A fast parameterized algorithm for Co-Path Set}, volume={63}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85014712605&partnerID=MN8TOARS}, DOI={10.4230/LIPIcs.IPEC.2016.28}, abstractNote={The k-CO-PATH SET problem asks, given a graph G and a positive integer k, whether one can delete k edges from G so that the remainder is a collection of disjoint paths. We give a linear-time fpt algorithm with complexity O^*(1.588^k) for deciding k-CO-PATH SET, significantly improving the previously best known O^*(2.17^k) of Feng, Zhou, and Wang (2015). Our main tool is a new O^*(4^{tw(G)}) algorithm for CO-PATH SET using the Cut&Count framework, where tw(G) denotes treewidth. In general graphs, we combine this with a branching algorithm which refines a 6k-kernel into reduced instances, which we prove have bounded treewidth.}, booktitle={Leibniz International Proceedings in Informatics, LIPIcs}, author={Sullivan, B.D. and Van Der Poel, A.}, year={2017} } @article{kloster_kuinke_o’brien_reidl_villaamil_sullivan_van der poel_2017, title={A practical fpt algorithm for flow decomposition and transcript assembly}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85094353595&partnerID=MN8TOARS}, journal={arXiv}, author={Kloster, K. and Kuinke, P. and O’Brien, M.P. and Reidl, F. and Villaamil, F.S. and Sullivan, B.D. and Van Der Poel, A.}, year={2017} } @article{o’brien_sullivan_2017, title={An experimental evaluation of a bounded expansion algorithmic pipeline}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85092949285&partnerID=MN8TOARS}, journal={arXiv}, author={O’Brien, M.P. and Sullivan, B.D.}, year={2017} } @inproceedings{asymptotic analysis of equivalences and core-structures in kronecker-style graph models_2017, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85014525949&partnerID=MN8TOARS}, DOI={10.1109/ICDM.2016.81}, booktitle={Proceedings - IEEE International Conference on Data Mining, ICDM}, year={2017}, pages={829–834} } @inproceedings{muzi_o’brien_reidl_sullivan_2017, title={Being even slightly shallow makes life hard}, volume={83}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85038445465&partnerID=MN8TOARS}, DOI={10.4230/LIPIcs.MFCS.2017.79}, abstractNote={We study the computational complexity of identifying dense substructures, namely $r/2$-shallow topological minors and $r$-subdivisions. Of particular interest is the case when $r=1$, when these substructures correspond to very localized relaxations of subgraphs. Since Densest Subgraph can be solved in polynomial time, we ask whether these slight relaxations also admit efficient algorithms. In the following, we provide a negative answer: Dense $r/2$-Shallow Topological Minor and Dense $r$-Subdivsion are already NP-hard for $r = 1$ in very sparse graphs. Further, they do not admit algorithms with running time $2^{o(\mathbf{tw}^2)} n^{O(1)}$ when parameterized by the treewidth of the input graph for $r \geq 2$ unless ETH fails.}, booktitle={Leibniz International Proceedings in Informatics, LIPIcs}, author={Muzi, I. and O’Brien, M.P. and Reidl, F. and Sullivan, B.D.}, year={2017} } @article{muzi_o’brien_reidl_sullivan_2017, title={Being even slightly shallow makes life hard}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85094429786&partnerID=MN8TOARS}, journal={arXiv}, author={Muzi, I. and O’Brien, M.P. and Reidl, F. and Sullivan, B.D.}, year={2017} } @article{goodrich_sullivan_humble_2017, title={Optimizing Adiabatic Quantum Program Compilation using a Graph-Theoretic Framework}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85095056109&partnerID=MN8TOARS}, journal={arXiv}, author={Goodrich, T.D. and Sullivan, B.D. and Humble, T.S.}, year={2017} } @article{kloster_král_sullivan_2017, title={Walk entropy and walk-regularity}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-85094268676&partnerID=MN8TOARS}, journal={arXiv}, author={Kloster, K. and Král, D. and Sullivan, B.D.}, year={2017} } @article{bridges_collins_ferragut_laska_sullivan_2016, title={A multi-level anomaly detection algorithm for time-varying graph data with interactive visualization}, volume={6}, ISSN={1869-5450 1869-5469}, url={http://dx.doi.org/10.1007/S13278-016-0409-Y}, DOI={10.1007/S13278-016-0409-Y}, abstractNote={This work presents a modeling and analysis framework for graph sequences which addresses the challenge of detecting and contextualizing anomalies in streaming graph data. Our goal is to detect changes at multiple levels of granularity, thereby identifying specific nodes and subgraphs causing a graph to appear anomalously. In particular, the framework detects changes in community membership, density, and node degree in a sequence of graphs where these are relatively stable. In route to this end, we introduce a new graph model, a generalization of the BTER model of Seshadhri et al., by adding flexibility to community structure, and use this model to perform multi-scale graph anomaly detection. This technique provides insight into a graph’s structure and internal context that may shed light on a detected event. Additionally, this multi-scale analysis facilitates intuitive visualizations by allowing users to narrow focus from an anomalous graph to particular subgraphs or nodes causing the anomaly. For evaluation, two hierarchical anomaly detectors are tested against a baseline Gaussian method on a series of sampled graphs. We demonstrate that our graph statistics-based approach outperforms both a distribution-based detector and the baseline in a labeled setting with community structure, and it accurately detects anomalies in synthetic and real-world datasets at the node, subgraph, and graph levels. To illustrate the accessibility of information made possible via this technique, the anomaly detector and an associated interactive visualization tool are tested on NCAA football data, where teams and conferences that moved within the league are identified with perfect recall, and precision >0.786.}, number={1}, journal={Social Network Analysis and Mining}, publisher={Springer Science and Business Media LLC}, author={Bridges, Robert A. and Collins, John and Ferragut, Erik M. and Laska, Jason and Sullivan, Blair D.}, year={2016}, month={Oct} } @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} } @article{adcock_sullivan_mahoney_2016, title={Tree decompositions and social graphs}, volume={12}, ISSN={["1944-9488"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84978531731&partnerID=MN8TOARS}, DOI={10.1080/15427951.2016.1182952}, abstractNote={Abstract Recent work has established that large informatics graphs such as social and information networks have non-trivial tree-like structure when viewed at moderate size scales. Here, we present results from the first detailed empirical evaluation of the use of tree decomposition (TD) heuristics for structure identification and extraction in social graphs. Although TDs have historically been used in structural graph theory and scientific computing, we show that—even with existing TD heuristics developed for those very different areas—TD methods can identify interesting structure in a wide range of realistic informatics graphs. Our main contributions are the following: we show that TD methods can identify structures that correlate strongly with the core-periphery structure of realistic networks, even when using simple greedy heuristics; we show that the peripheral bags of these TDs correlate well with low-conductance communities (when they exist) found using local spectral computations; and we show that several types of large-scale “ground-truth” communities, defined by demographic metadata on the nodes of the network, are well-localized in the large-scale and/or peripheral structures of the TDs. Our other main contributions are the following: we provide detailed empirical results for TD heuristics on toy and synthetic networks to establish a baseline to understand better the behavior of the heuristics on more complex real-world networks; and we prove a theorem providing formal justification for the intuition that the only two impediments to low-distortion hyperbolic embedding are high tree-width and long geodesic cycles. Our results suggest future directions for improved TD heuristics that are more appropriate for realistic social graphs.}, number={5}, journal={INTERNET MATHEMATICS}, author={Adcock, Aaron B. and Sullivan, Blair D. and Mahoney, Michael W.}, year={2016}, pages={315–361} } @article{farrell_goodrich_lemons_reidl_villaamil_sullivan_2015, title={Hyperbolicity, Degeneracy, and Expansion of Random Intersection Graphs}, volume={9479}, ISBN={["978-3-319-26783-8"]}, ISSN={["1611-3349"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84951869780&partnerID=MN8TOARS}, DOI={10.1007/978-3-319-26784-5_3}, abstractNote={We establish the conditions under which several algorithmically exploitable structural features hold for random intersection graphs, a natural model for many real-world networks where edges correspond to shared attributes. Specifically, we fully characterize the degeneracy of random intersection graphs, and prove that the model asymptotically almost surely produces graphs with hyperbolicity at least $$\log {n}$$ . Further, we prove that when degenerate, the graphs generated by this model belong to a bounded-expansion graph class with high probability, a property particularly suitable for the design of linear time algorithms.}, journal={ALGORITHMS AND MODELS FOR THE WEB GRAPH, (WAW 2015)}, author={Farrell, Matthew and Goodrich, Timothy D. and Lemons, Nathan and Reidl, Felix and Villaamil, Fernando Sanchez and Sullivan, Blair D.}, year={2015}, pages={29–41} } @article{bridges_collins_ferragut_laska_sullivan_2015, title={Multi-Level Anomaly Detection on Time-Varying Graph Data}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84962580244&partnerID=MN8TOARS}, DOI={10.1145/2808797.2809406}, abstractNote={This work presents a novel modeling and analysis framework for graph sequences which addresses the challenge of detecting and contextualizing anomalies in labeled, streaming graph data. We introduce a generalization of the BTER model of Seshadhri et al. by adding flexibility to community structure, and use this model to perform multi-scale graph anomaly detection. Specifically, probability models describing coarse subgraphs are built by aggregating node probabilities, and these related hierarchical models simultaneously detect deviations from expectation. This technique provides insight into the graphs' structure and helps contextualized detected event. For evaluation, two new hierarchical detectors are tested against a baseline Gaussian method on a synthetic graph sequence with seeded anomalies. We demonstrate that in a labeled setting with community structure, our graph statistics-based approach outperforms both a distribution-based detector and the baseline, accurately detecting anomalies at the node, subgraph, and graph levels.}, journal={PROCEEDINGS OF THE 2015 IEEE/ACM INTERNATIONAL CONFERENCE ON ADVANCES IN SOCIAL NETWORKS ANALYSIS AND MINING (ASONAM 2015)}, author={Bridges, Robert A. and Collins, John P. and Ferragut, Erik M. and Laska, Jason A. and Sullivan, Blair D.}, year={2015}, pages={579–583} } @article{drange_dregi_lokshtanov_sullivan_2015, title={On the Threshold of Intractability}, volume={9294}, ISBN={["978-3-662-48349-7"]}, ISSN={["1611-3349"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84945584240&partnerID=MN8TOARS}, DOI={10.1007/978-3-662-48350-3_35}, abstractNote={We study the computational complexity of the graph modification problems and , adding and deleting as few edges as possible to transform the input into a threshold (or chain) graph. In this article, we show that both problems are -hard, resolving a conjecture by Natanzon, Shamir, and Sharan (2001). On the positive side, we show that these problems admit quadratic vertex kernels. Furthermore, we give a subexponential time parameterized algorithm solving in time, making it one of relatively few natural problems in this complexity class on general graphs. These results are of broader interest to the field of social network analysis, where recent work of Brandes (2014) posits that the minimum edit distance to a threshold graph gives a good measure of consistency for node centralities. Finally, we show that all our positive results extend to , as well as the completion and deletion variants of both problems.}, journal={ALGORITHMS - ESA 2015}, author={Drange, Pal Gronas and Dregi, Markus Sortland and Lokshtanov, Daniel and Sullivan, Blair D.}, year={2015}, pages={411–423} } @article{zig-zag numberlink is np-complete_2015, volume={23}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84929412116&partnerID=MN8TOARS}, DOI={10.2197/ipsjjip.23.239}, abstractNote={When can $t$ terminal pairs in an $m \times n$ grid be connected by $t$ vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the ``cover all vertices'' constraint, and Kotsuma and Takenaga's 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class. The latter restriction is a common form of the famous Nikoli puzzle \emph{Numberlink}; our problem is another common form of Numberlink, sometimes called \emph{Zig-Zag Numberlink} and popularized by the smartphone app \emph{Flow Free}.}, number={3}, journal={Journal of Information Processing}, year={2015}, pages={239–245} } @article{humble_mccaskey_bennink_billings_dazevedo_sullivan_klymko_seddiqi_2014, title={An integrated programming and development environment for adiabatic quantum optimization}, volume={7}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84920520607&partnerID=MN8TOARS}, DOI={10.1088/1749-4680/7/1/015006}, abstractNote={Adiabatic quantum computing is a promising route to the computational power afforded by quantum information processing. The recent availability of adiabatic hardware has raised challenging questions about how to evaluate adiabatic quantum optimization (AQO) programs. Processor behavior depends on multiple steps to synthesize an adiabatic quantum program, which are each highly tunable. We present an integrated programming and development environment for AQO called Jade Adiabatic Development Environment (JADE) that provides control over all the steps taken during program synthesis. JADE captures the workflow needed to rigorously specify the AQO algorithm while allowing a variety of problem types, programming techniques, and processor configurations. We have also integrated JADE with a quantum simulation engine that enables program profiling using numerical calculation. The computational engine supports plug-ins for simulation methodologies tailored to various metrics and computing resources. We present the design, integration, and deployment of JADE and discuss its potential use for benchmarking AQO programs by the quantum computer science community.}, number={1}, journal={Computational Science and Discovery}, author={Humble, T.S. and McCaskey, A.J. and Bennink, R.S. and Billings, J.J. and Dazevedo, E.D. and Sullivan, B.D. and Klymko, C.F. and Seddiqi, H.}, year={2014} } @inproceedings{obrien_sullivan_2014, title={Locally Estimating Core Numbers}, volume={2015-January}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84936947120&partnerID=MN8TOARS}, DOI={10.1109/ICDM.2014.136}, abstractNote={Graphs are a powerful way to model interactions and relationships in data from a wide variety of application domains. In this setting, entities represented by vertices at the 'center' of the graph are often more important than those associated with vertices on the 'fringes'. For example, central nodes tend to be more critical in the spread of information or disease and play an important role in clustering/community formation. Identifying such 'core' vertices has recently received additional attention in the context of network experiments, which analyze the response when a random subset of vertices are exposed to a treatment (e.g. Inoculation, free product samples, etc). Specifically, the likelihood of having many central vertices in any exposure subset can have a significant impact on the experiment. We focus on using k-cores and core numbers to measure the extent to which a vertex is central in a graph. Existing algorithms for computing the core number of a vertex require the entire graph as input, an unrealistic scenario in many real world applications. Moreover, in the context of network experiments, the sub graph induced by the treated vertices is only known in a probabilistic sense. We introduce a new method for estimating the core number based only on the properties of the graph within a region of radius δ around the vertex, and prove an asymptotic error bound of our estimator on random graphs. Further, we empirically validate the accuracy of our estimator for small values of δ on a representative corpus of real data sets. Finally, we evaluate the impact of improved local estimation on an open problem in network experimentation posed by Ugander et al.}, number={January}, booktitle={Proceedings - IEEE International Conference on Data Mining, ICDM}, author={Obrien, M.P. and Sullivan, B.D.}, year={2014}, pages={460–469} } @article{klymko_sullivan_humble_2013, title={Adiabatic quantum programming: minor embedding with hard faults}, volume={13}, ISSN={1570-0755 1573-1332}, url={http://dx.doi.org/10.1007/S11128-013-0683-9}, DOI={10.1007/s11128-013-0683-9}, abstractNote={Adiabatic quantum programming defines the time-dependent mapping of a quantum algorithm into an underlying hardware or logical fabric. An essential step is embedding problem-specific information into the quantum logical fabric. We present algorithms for embedding arbitrary instances of the adiabatic quantum optimization algorithm into a square lattice of specialized unit cells. These methods extend with fabric growth while scaling linearly in time and quadratically in footprint. We also provide methods for handling hard faults in the logical fabric without invoking approximations to the original problem and illustrate their versatility through numerical studies of embeddability versus fault rates in square lattices of complete bipartite unit cells. The studies show that these algorithms are more resilient to faulty fabrics than naive embedding approaches, a feature which should prove useful in benchmarking the adiabatic quantum optimization algorithm on existing faulty hardware.}, number={3}, journal={Quantum Information Processing}, publisher={Springer Science and Business Media LLC}, author={Klymko, Christine and Sullivan, Blair D. and Humble, Travis S.}, year={2013}, month={Nov}, pages={709–729} } @inbook{adcock_sullivan_hernandez_mahoney_2013, title={Evaluating OpenMP Tasking at Scale for the Computation of Graph Hyperbolicity}, volume={8122 LNCS}, ISBN={9783642406973 9783642406980}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-642-40698-0_6}, DOI={10.1007/978-3-642-40698-0_6}, abstractNote={We describe using OpenMP to compute δ-hyperbolicity, a quantity of interest in social and information network analysis, at a scale that uses up to 1000 threads. By considering both OpenMP workshare and tasking models to parallelize the computations, we find that multiple task levels permits finer grained tasks at runtime and results in better performance at scale than worksharing constructs. We also characterize effects of task inflation, load balancing, and scheduling overhead in this application, using both GNU and Intel compilers. Finally, we show how OpenMP 3.1 tasking clauses can be used to mitigate overheads at scale.}, booktitle={OpenMP in the Era of Low Power Devices and Accelerators}, publisher={Springer Berlin Heidelberg}, author={Adcock, Aaron B. and Sullivan, Blair D. and Hernandez, Oscar R. and Mahoney, Michael W.}, year={2013}, pages={71–83} } @article{sullivan_2013, title={On a conjecture of Andrica and Tomescu}, volume={16}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84880061040&partnerID=MN8TOARS}, number={3}, journal={Journal of Integer Sequences}, author={Sullivan, B.D.}, year={2013} } @inproceedings{sullivan_weerapurage_groer_2013, title={Parallel algorithms for graph optimization using tree decompositions}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84899764118&partnerID=MN8TOARS}, DOI={10.1109/IPDPSW.2013.242}, abstractNote={Although many NP-hard graph optimization problems can be solved in polynomial time on graphs of bounded tree-width, the adoption of these techniques into mainstream scientific computation has been limited due to the high memory requirements of the dynamic programming tables and excessive runtimes of sequential implementations. This work addresses both challenges by proposing a set of new parallel algorithms for all steps of a tree decomposition-based approach to solve the maximum weighted independent set problem. A hybrid OpenMP/MPI implementation includes a highly scalable parallel dynamic programming algorithm leveraging the MADNESS task based runtime, and computational results demonstrate scaling. This work enables a significant expansion of the scale of graphs on which exact solutions to maximum weighted independent set can be obtained, and forms a framework for solving additional graph optimization problems with similar techniques.}, booktitle={Proceedings - IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, IPDPSW 2013}, author={Sullivan, B.D. and Weerapurage, D. and Groer, C.}, year={2013}, pages={1838–1847} } @inproceedings{adcock_sullivan_mahoney_2013, title={Tree-Like Structure in Large Social and Information Networks}, url={http://dx.doi.org/10.1109/icdm.2013.77}, DOI={10.1109/icdm.2013.77}, abstractNote={Although large social and information networks are often thought of as having hierarchical or tree-like structure, this assumption is rarely tested. We have performed a detailed empirical analysis of the tree-like properties of realistic informatics graphs using two very different notions of tree-likeness: Gromov's d-hyperbolicity, which is a notion from geometric group theory that measures how tree-like a graph is in terms of its metric structure, and tree decompositions, tools from structural graph theory which measure how tree-like a graph is in terms of its cut structure. Although realistic informatics graphs often do not have meaningful tree-like structure when viewed with respect to the simplest and most popular metrics, e.g., the value of d or the tree width, we conclude that many such graphs do have meaningful tree-like structure when viewed with respect to more refined metrics, e.g., a size-resolved notion of d or a closer analysis of the tree decompositions. We also show that, although these two rigorous notions of tree-likeness capture very different tree-like structures in worst-case, for realistic informatics graphs they empirically identify surprisingly similar structure. We interpret this tree-like structure in terms of the recently-characterized "nested core-periphery" property of large informatics graphs, and we show that the fast and scalable k-core heuristic can be used to identify this tree-like structure.}, booktitle={2013 IEEE 13th International Conference on Data Mining}, publisher={IEEE}, author={Adcock, Aaron B. and Sullivan, Blair D. and Mahoney, Michael W.}, year={2013}, month={Dec}, pages={1–10} } @article{groër_sullivan_poole_2011, title={A mathematical analysis of the R-MAT random graph generator}, volume={58}, ISSN={0028-3045}, url={http://dx.doi.org/10.1002/net.20417}, DOI={10.1002/net.20417}, abstractNote={Abstract}, number={3}, journal={Networks}, publisher={Wiley}, author={Groër, Chris and Sullivan, Blair D. and Poole, Steve}, year={2011}, month={Apr}, pages={159–170} } @article{seymour_sullivan_2010, title={Counting paths in digraphs}, volume={31}, ISSN={0195-6698}, url={http://dx.doi.org/10.1016/j.ejc.2009.05.008}, DOI={10.1016/j.ejc.2009.05.008}, abstractNote={Say a digraph is k-free if it has no directed cycles of length at most k, for positive integers k. Thomasse conjectured that the number of induced 3-vertex directed paths in a simple 2-free digraph on n vertices is at most (n-1)n(n+1)/15. We present an unpublished result of Bondy proving that there are at most 2n^3/25 such paths, and prove that for the class of circular interval digraphs, an upper bound of n^3/16 holds. We also study the problem of bounding the number of (non-induced) 4-vertex paths in 3-free digraphs. We show an upper bound of 4n^4/75 using Bondy's result for Thomasse's conjecture.}, number={3}, journal={European Journal of Combinatorics}, publisher={Elsevier BV}, author={Seymour, Paul and Sullivan, Blair D.}, year={2010}, month={Apr}, pages={961–975} } @article{chudnovsky_seymour_sullivan_2008, title={Cycles in dense digraphs}, volume={28}, ISSN={0209-9683 1439-6912}, url={http://dx.doi.org/10.1007/S00493-008-2331-Z}, DOI={10.1007/S00493-008-2331-Z}, number={1}, journal={Combinatorica}, publisher={Springer Science and Business Media LLC}, author={Chudnovsky, Maria and Seymour, Paul and Sullivan, Blair}, year={2008}, month={Jan}, pages={1–18} }