Works (58)

Updated: September 23rd, 2024 08:17

2022 article

Faster Decomposition ofWeighted Graphs into Cliques using Fisher's Inequality

ArXiv.

By: S. Jain, Y. Mizutani & B. Sullivan*

Contributors: S. Jain, Y. Mizutani & B. Sullivan*

Source: ORCID
Added: August 6, 2022

2022 article

Gerrymandering Trees: Parameterized Hardness

ArXiv.

By: A. Fraser, B. Lavallee & B. Sullivan*

Contributors: A. Fraser, B. Lavallee & B. Sullivan*

UN Sustainable Development Goal Categories
16. Peace, Justice and Strong Institutions (OpenAlex)
Source: ORCID
Added: August 6, 2022

2022 article

Improved Parameterized Complexity of Happy Set Problems

ArXiv.

By: Y. Mizutani & B. Sullivan*

Contributors: Y. Mizutani & B. Sullivan*

Source: ORCID
Added: August 6, 2022

2021 journal article

An Updated Experimental Evaluation of Graph Bipartization Methods

ACM Journal of Experimental Algorithmics, 26.

By: T. Goodrich n, E. Horton n & B. Sullivan n

Contributors: T. Goodrich n, E. Horton n & B. Sullivan n

TL;DR: It is found that for heuristic solutions with time constraints under a second, iterative compression routines jump-started with a heuristic solution perform best, after which point using a highly tuned solver like CPLEX is worthwhile. (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2021 article

Hardness of the Generalized Coloring Numbers

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85121786987&partnerID=MN8TOARS

By: M. Breen-McKay, B. Lavallee & B. Sullivan

Contributors: M. Breen-McKay, B. Lavallee & B. Sullivan

Source: ORCID
Added: August 6, 2022

2021 journal article

On the threshold of intractability

Journal of Computer and System Sciences, 124, 1–25.

By: P. Drange*, M. Dregi*, D. Lokshtanov* & B. Sullivan*

Contributors: P. Drange*, M. Dregi*, D. Lokshtanov* & B. Sullivan*

author keywords: Edge editing; Threshold graphs; Parameterized complexity
Source: ORCID
Added: August 6, 2022

2021 conference paper

Parameterized algorithms for identifying gene co-expression modules via weighted clique decomposition

SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21), 111–122.

By: M. Cooley, C. Greene, D. Issac, M. Pividori* & B. Sullivan*

Contributors: B. Sullivan*

TL;DR: A new combinatorial model for identifying regulatory modules in gene co-expression data using a decomposition into weighted cliques is presented, and two new algorithms for finding these decompositions are presented, using linear programming and integer partitioning to determine the clique weights. (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2021 article

Parameterized algorithms for identifying gene co-expression modules via weighted clique decomposition

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85108789587&partnerID=MN8TOARS

By: M. Cooley, C. Greene, D. Issac, M. Pividori & B. Sullivan

Contributors: M. Cooley, C. Greene, D. Issac, M. Pividori & B. Sullivan

Source: ORCID
Added: August 6, 2022

2021 article

Projecting genetic associations through gene expression patterns highlights disease etiology and drug mechanisms

BioRxiv.

Contributors: M. Pividori*, S. Lu*, B. Li*, C. Su*, M. Johnson*, W. Wei*, Q. Feng*, B. Namjou* ...

TL;DR: PhenoPLIER is introduced, a computational approach that maps gene-trait associations and pharmacological perturbation data into a common latent representation for a joint analysis that is accurate in predicting known drug-disease pairs and inferring mechanisms of action. (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2021 article

Sparse dominating sets and balanced neighborhood partitioning

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85121833484&partnerID=MN8TOARS

By: Y. Mizutani, A. Staker & B. Sullivan

Contributors: Y. Mizutani, A. Staker & B. Sullivan

Source: ORCID
Added: August 6, 2022

2020 article

A color-avoiding approach to subgraph counting in bounded expansion classes

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85095561220&partnerID=MN8TOARS

By: F. Reidl & B. Sullivan

Contributors: F. Reidl & B. Sullivan

Source: ORCID
Added: August 6, 2022

2020 journal article

Exploring neighborhoods in large metagenome assembly graphs using spacegraphcats reveals hidden sequence diversity

GENOME BIOLOGY, 21(1).

Contributors: C. Brown*, D. Moritz*, . M.P. O'Brien, F. Reidl n, T. Reiter* & B. Sullivan n

author keywords: Metagenomics; Sequence assembly; Strain variation; Bounded expansion; Dominating set
MeSH headings : Algorithms; Genetic Variation; Genome; Metagenomics / methods; Software
TL;DR: 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 is introduced. (via Semantic Scholar)
Sources: Web Of Science, NC State University Libraries, ORCID
Added: August 10, 2020

2020 journal article

Polynomial Treedepth Bounds in Linear Colorings

ALGORITHMICA, 83(1), 361–386.

By: J. Kun*, . Michael P. O'Brien n, M. Pilipczuk* & B. Sullivan n

Contributors: J. Kun*, M. O’Brien n, M. Pilipczuk* & B. Sullivan n

author keywords: Linear colorings; p-centered colorings; Bounded expansion; Treedepth
TL;DR: A polynomial upper bound on the treedepth in general graphs is established, and tighter bounds in trees and interval graphs via constructive coloring algorithms are given via constructive coloring algorithms. (via Semantic Scholar)
Sources: Web Of Science, ORCID, NC State University Libraries
Added: September 21, 2020

2020 chapter

Secondary Structure Ensemble Analysis via Community Detection

In Association for Women in Mathematics Series (Vol. 22, pp. 55–81).

By: H. Du*, M. Ferrari*, C. Heitsch*, F. Hurley n, C. Mennicke n, B. Sullivan*, B. Xu*

Contributors: H. Du*, M. Ferrari*, C. Heitsch*, F. Hurley n, C. Mennicke n, B. Sullivan*, B. Xu*

Source: ORCID
Added: August 6, 2022

2019 conference paper

Approximating vertex cover using structural rounding

Proceedings of the Workshop on Algorithm Engineering and Experiments, 2020-January, 70–80.

By: B. Lavallee*, H. Russell*, B. Sullivan* & A. Poel*

Contributors: B. Lavallee*, H. Russell*, B. Sullivan* & A. Poel*

TL;DR: This work provides the first practical evaluation of the structural rounding framework for approximation algorithms, and finds that in this setting, structural rounding significantly outperforms standard 2-approximations. (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2019 article

Approximating vertex cover using structural rounding

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85094768942&partnerID=MN8TOARS

By: B. Lavallee, H. Russell, B. Sullivan & A. Poel

Contributors: B. Lavallee, H. Russell, B. Sullivan & A. Poel

Source: ORCID
Added: August 6, 2022

2019 article

Faster Biclique Mining in Near-Bipartite Graphs

ANALYSIS OF EXPERIMENTAL ALGORITHMS, SEA2 2019, Vol. 11544, pp. 424–453.

By: B. Sullivan n, A. Poel n & T. Woodlief n

Contributors: B. Sullivan n, A. Poel n & T. Woodlief n

author keywords: Bicliques; Odd cycle transversal; Bipartite; Enumeration algorithms; Parameterized complexity
TL;DR: Two new algorithms optimized for near-bipartite graphs are introduced - one which enumerates MIBs in time O(M_I |V||E| k), and another based on the approach of Alexe et al. which enumeration of all maximal bicliques in time M_I and M_B, where M-I andM_B denote the number of M IBs and MBs in the graph, respectively. (via Semantic Scholar)
Sources: Web Of Science, NC State University Libraries, ORCID
Added: November 16, 2020

2019 conference paper

Mining maximal induced bicliques using odd cycle transversals

SIAM International Conference on Data Mining, SDM 2019, 324–332.

By: K. Kloster, A. Poel & B. Sullivan*

Contributors: K. Kloster, A. Poel & B. Sullivan*

TL;DR: A new algorithm for enumerating MIBs in general graphs, whose run time depends on how "close to bipartite" the input is, and the runtime is parameterized by the size k of an odd cycle transversal (OCT), a vertex set whose deletion results in a bipartITE graph. (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2019 article

Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class

27TH ANNUAL EUROPEAN SYMPOSIUM ON ALGORITHMS (ESA 2019), Vol. 144.

By: E. Demaine, T. Goodrich, K. Kloster, B. Lavallee, Q. Liu, B. Sullivan, A. Vakilian, A. Poel

Contributors: E. Demaine, T. Goodrich, K. Kloster, B. Lavallee, Q. Liu, B. Sullivan, A. Vakilian, A. Poel

author keywords: structural rounding; graph editing; approximation algorithms
TL;DR: New editing algorithms are developed that find the approximately-fewest edits required to bring a given graph into one of several important graph classes (in some cases, also approximating the target parameter of the family). (via Semantic Scholar)
UN Sustainable Development Goal Categories
Sources: Web Of Science, NC State University Libraries, ORCID
Added: October 5, 2020

2019 journal article

Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs

Journal of Computer and System Sciences, 105, 199–241.

By: E. Demaine*, F. Reidl*, P. Rossmanith*, F. Villaamil*, S. Sikdar* & B. Sullivan n

Contributors: E. Demaine*, F. Reidl*, P. Rossmanith*, F. Sánchez Villaamil*, S. Sikdar* & B. Sullivan n

author keywords: Structural sparsity; Bounded expansion; Complex networks; Random graphs; Motif counting; Centrality measures
TL;DR: This research establishes that many real-world networks exhibit bounded expansion, a strong notion of structural sparsity, and demonstrates that it can be leveraged to design efficient algorithms for network analysis, and supports the findings with empirical measurements on a corpus of real- world networks. (via Semantic Scholar)
Source: ORCID
Added: May 25, 2019

2019 journal article

Subgraph centrality and walk-regularity

Linear Algebra and Its Applications, 570, 225–244.

By: E. Horton n, K. Kloster n & B. Sullivan n

Contributors: E. Horton n, K. Kloster n & B. Sullivan n

author keywords: Centrality; Graph entropy; Walk-regularity; Functions of matrices; Network analysis
TL;DR: This work considers when non--walk-regular graphs can achieve maximum entropy, calling such graphs $\textit{entropic}$, and builds infinite families of entropic graphs, as well as a family of witnessing parameters with a limit point at zero. (via Semantic Scholar)
Source: ORCID
Added: February 12, 2019

2018 conference paper

A practical fpt algorithm for flow decomposition and transcript assembly

Proceedings of the Workshop on Algorithm Engineering and Experiments, 2018-January, 75–86.

By: K. Kloster, P. Kuinke, M. O?Brien, F. Reidl, F. Villaamil, B. Sullivan*, A. Van Der Poel

Contributors: K. Kloster, P. Kuinke, M. O’Brien, F. Reidl, F. Villaamil, B. Sullivan*, A. Van Der Poel

TL;DR: The Flow Decomposition problem, which asks for the smallest set of weighted paths that "covers" a flow on a DAG, has recently been used as an important computational step in transcript assembly and it is proved the problem is in FPT when parameterized by the number of paths by giving a practical linear fpt algorithm. (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2018 article

An updated experimental evaluation of graph bipartization methods

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85104339918&partnerID=MN8TOARS

By: T. Goodrich, E. Horton & B. Sullivan

Contributors: T. Goodrich, E. Horton & B. Sullivan

Source: ORCID
Added: August 6, 2022

2018 journal article

Benchmarking treewidth as a practical component of tensor network simulations

PLOS ONE, 13(12).

By: E. Dumitrescu*, A. Fisher n, T. Goodrich n, T. Humble*, B. Sullivan n & A. Wright n

Contributors: E. Dumitrescu*, A. Fisher n, T. Goodrich n, T. Humble*, B. Sullivan n & A. Wright n

Ed(s): E. Torre

MeSH headings : Algorithms; Benchmarking; Computer Graphics; Computer Simulation; Quantum Theory; Software
TL;DR: This work exhibits multiple regimes where treewidth-based algorithms outperform domain-specific algorithms, while demonstrating that the optimal choice of algorithm has a complex dependence on the network density, expected contraction complexity, and user run time requirements. (via Semantic Scholar)
Sources: Web Of Science, ORCID, NC State University Libraries
Added: January 7, 2019

2018 article

Benchmarking treewidth as a practical component of tensor-network–based quantum simulation

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85095245427&partnerID=MN8TOARS

By: E. Dumitrescu, A. Fisher, T. Goodrich, T. Humble, B. Sullivan & A. Wrigh

Contributors: E. Dumitrescu, A. Fisher, T. Goodrich, T. Humble, B. Sullivan & A. Wrigh

Source: ORCID
Added: August 6, 2022

2018 article

Exploring neighborhoods in large metagenome assembly graphs reveals hidden sequence diversity

Brown, C. T., Moritz, D., O’Brien, M. P., Reidl, F., Reiter, T., & Sullivan, B. D. (2018, November 5). BioRxiv, Vol. 11.

By: C. Brown, D. Moritz*, M. O’Brien*, F. Reidl*, T. Reiter & B. Sullivan*

Contributors: C. Brown, D. Moritz*, M. O’Brien*, F. Reidl*, T. Reiter & B. Sullivan*

TL;DR: An information retrieval system for large metagenomic data sets that exploits the sparsity of DNA assembly graphs to efficiently extract subgraphs surround-ing an inferred genome is introduced. (via Semantic Scholar)
Source: ORCID
Added: February 8, 2019

2018 article

Mining maximal induced bicliques using odd cycle transversals

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85093320378&partnerID=MN8TOARS

By: K. Kloster, B. Sullivan & A. Van Der Poel

Contributors: K. Kloster, B. Sullivan & A. Van Der Poel

Source: ORCID
Added: August 6, 2022

2018 journal article

Optimizing adiabatic quantum program compilation using a graph-theoretic framework

Quantum Information Processing, 17(5).

By: T. Goodrich n, B. Sullivan n & T. Humble*

Contributors: T. Goodrich n, B. Sullivan n & T. Humble*

TL;DR: This work develops a new baseline for embedding a wide range of optimization problems into fault-free D-Wave annealing hardware, and introduces a graph-theoretic framework for developing structured embedding algorithms. (via Semantic Scholar)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020

2018 article

Polynomial treedepth bounds in linear colorings

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85092833264&partnerID=MN8TOARS

By: J. Kun, M. O’Brien, M. Pilipczuk & B. Sullivan

Contributors: J. Kun, . M.P. O'Brien, M. Pilipczuk & B. Sullivan

Source: ORCID
Added: August 6, 2022

2018 article

Structural rounding: Approximation algorithms for graphs near an algorithmically tractable class

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85094277709&partnerID=MN8TOARS

By: E. Demaine, T. Goodrich, K. Kloster, B. Lavallee, Q. Liu, B. Sullivan, A. Vakilian, A. Poel

Contributors: E. Demaine, T. Goodrich, K. Kloster, B. Lavallee, Q. Liu, B. Sullivan, A. Vakilian, A. Poel

Source: ORCID
Added: August 6, 2022

2018 article

Subgraph centrality and walk-regularity

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85093754399&partnerID=MN8TOARS

By: E. Horton, K. Kloster & B. Sullivan

Contributors: E. Horton, K. Kloster & B. Sullivan

Source: ORCID
Added: August 6, 2022

2018 chapter

Treedepth Bounds in Linear Colorings

In Graph-Theoretic Concepts in Computer Science: Vol. 11159 LNCS (pp. 331–343).

By: J. Kun*, M. O’Brien n & B. Sullivan n

Contributors: J. Kun*, M. O’Brien n & B. Sullivan n

TL;DR: Low-treedepth colorings are introduced as an alternative to the commonly used p-centered colorings and a co-NP-completeness reduction is given for recognizing p-linear colorings, and polynomial upper bounds are established via constructive coloring algorithms in trees and intervals graphs and it is conjecture that aPolynomial relationship is in fact the worst case in general graphs. (via Semantic Scholar)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020

2018 journal article

Walk entropy and walk-regularity

Linear Algebra and Its Applications, 546, 115–121.

By: K. Kloster n, D. Král'* & B. Sullivan n

Contributors: K. Kloster n, D. Král* & B. Sullivan n

author keywords: Graph entropy; Walk-regularity; Subgraph centrality; Matrix exponential
Source: ORCID
Added: February 8, 2019

2017 article

A practical fpt algorithm for flow decomposition and transcript assembly

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85094353595&partnerID=MN8TOARS

By: K. Kloster, P. Kuinke, M. O’Brien, F. Reidl, F. Villaamil, B. Sullivan, A. Van Der Poel

Contributors: K. Kloster, P. Kuinke, . M.P. O'Brien, F. Reidl, F. Villaamil, B. Sullivan, A. Van Der Poel

Source: ORCID
Added: August 6, 2022

2017 article

An experimental evaluation of a bounded expansion algorithmic pipeline

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85092949285&partnerID=MN8TOARS

By: M. O’Brien & B. Sullivan

Contributors: . M.P. O'Brien & B. Sullivan

Source: ORCID
Added: August 6, 2022

2017 conference paper

Asymptotic analysis of equivalences and core-structures in kronecker-style graph models

Proceedings - IEEE International Conference on Data Mining, ICDM, 829–834.

Contributors: A. Chin, T. Goodrich, . M.P. O'Brien, F. Reidl, B. Sullivan & A. Van Der Poel

Source: ORCID
Added: August 6, 2022

2017 conference paper

Being even slightly shallow makes life hard

Leibniz International Proceedings in Informatics, LIPIcs, 83.

By: I. Muzi*, M. O’Brien n, F. Reidl* & B. Sullivan n

Contributors: I. Muzi*, . M.P. O'Brien, F. Reidl* & B. Sullivan n

TL;DR: Dense $r/2$-Shallow Topological Minor and Dense £r-Subdivsion are already NP-hard for r = 1$ in very sparse graphs and 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. (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2017 article

Being even slightly shallow makes life hard

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85094429786&partnerID=MN8TOARS

By: I. Muzi, M. O’Brien, F. Reidl & B. Sullivan

Contributors: I. Muzi, . M.P. O'Brien, F. Reidl & B. Sullivan

Source: ORCID
Added: August 6, 2022

2017 article

Optimizing Adiabatic Quantum Program Compilation using a Graph-Theoretic Framework

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85095056109&partnerID=MN8TOARS

By: T. Goodrich, B. Sullivan & T. Humble

Contributors: T. Goodrich, B. Sullivan & T. Humble

Source: ORCID
Added: August 6, 2022

2017 article

Walk entropy and walk-regularity

ArXiv. http://www.scopus.com/inward/record.url?eid=2-s2.0-85094268676&partnerID=MN8TOARS

By: K. Kloster, D. Král & B. Sullivan

Contributors: K. Kloster, D. Král & B. Sullivan

Source: ORCID
Added: August 6, 2022

2016 conference paper

A fast parameterized algorithm for Co-Path Set

Leibniz International Proceedings in Informatics, LIPIcs, 63.

By: B. Sullivan n & A. Van Der Poel n

Contributors: B. Sullivan n & A. Van Der Poel n

TL;DR: A linear-time fpt algorithm with complexity O^*(1.588^k) for deciding k-CO-PATH SET is given, significantly improving the previously best known O*(2.17^ k) of Feng, Zhou, and Wang (2015). (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2016 journal article

A multi-level anomaly detection algorithm for time-varying graph data with interactive visualization

Social Network Analysis and Mining, 6(1).

By: R. Bridges*, J. Collins*, E. Ferragut*, J. Laska* & B. Sullivan n

Contributors: R. Bridges*, J. Collins*, E. Ferragut*, J. Laska* & B. Sullivan n

author keywords: Anomaly detection; Graph sequence; Visualization
TL;DR: A new graph model is introduced, a generalization of the BTER model of Seshadhri et al., by adding flexibility to community structure, and this model is used to perform multi-scale graph anomaly detection and provides insight into a graph’s structure and internal context that may shed light on a detected event. (via Semantic Scholar)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020

2016 conference paper

Asymptotic analysis of equivalences and core-structures in Kronecker-style graph models

2016 ieee 16th international conference on data mining (icdm), 829–834.

By: A. Chin*, T. Goodrich n, M. O'Brien n, F. Reidl n, B. Sullivan n & A. Poel n

TL;DR: It is proved that although several R-MAT formulations are asymptotically equivalent, their behaviour is different from that of SKG, and a case where asymPTotic analysis reveals unexpected behavior within a given model is considered. (via Semantic Scholar)
Sources: NC State University Libraries, NC State University Libraries, ORCID
Added: August 6, 2018

2016 journal article

Tree decompositions and social graphs

INTERNET MATHEMATICS, 12(5), 315–361.

By: A. Adcock*, B. Sullivan n & M. Mahoney*

Contributors: A. Adcock*, B. Sullivan n & M. Mahoney*

TL;DR: It is shown that TD methods can identify structures that correlate strongly with the core-periphery structure of realistic networks, even when using simple greedy heuristics; and it is proved that the only two impediments to low-distortion hyperbolic embedding are high tree-width and long geodesic cycles. (via Semantic Scholar)
Sources: Web Of Science, NC State University Libraries, ORCID
Added: August 6, 2018

2015 article

Hyperbolicity, Degeneracy, and Expansion of Random Intersection Graphs

ALGORITHMS AND MODELS FOR THE WEB GRAPH, (WAW 2015), Vol. 9479, pp. 29–41.

By: M. Farrell*, T. Goodrich n, N. Lemons*, F. Reidl*, F. Villaamil* & B. Sullivan n

Contributors: M. Farrell*, T. Goodrich n, N. Lemons*, F. Reidl*, F. Villaamil* & B. Sullivan n

Sources: Web Of Science, NC State University Libraries, ORCID
Added: August 6, 2018

2015 article

Multi-Level Anomaly Detection on Time-Varying Graph Data

PROCEEDINGS OF THE 2015 IEEE/ACM INTERNATIONAL CONFERENCE ON ADVANCES IN SOCIAL NETWORKS ANALYSIS AND MINING (ASONAM 2015), pp. 579–583.

By: R. Bridges*, J. Collins*, E. Ferragut*, J. Laska* & B. Sullivan n

Contributors: R. Bridges*, J. Collins*, E. Ferragut*, J. Laska* & B. Sullivan n

TL;DR: This work introduces a generalization of the BTER model of Seshadhri et al. by adding flexibility to community structure, and uses this model to perform multi-scale graph anomaly detection, accurately detecting anomalies at the node, subgraph, and graph levels. (via Semantic Scholar)
Sources: Web Of Science, NC State University Libraries, ORCID
Added: August 6, 2018

2015 article

On the Threshold of Intractability

ALGORITHMS - ESA 2015, Vol. 9294, pp. 411–423.

By: P. Drange*, M. Dregi*, D. Lokshtanov* & B. Sullivan n

Contributors: P. Drange*, M. Dregi*, D. Lokshtanov* & B. Sullivan n

TL;DR: This article shows that both graph modification problems are Open image in new window -hard, resolving a conjecture by Natanzon, Shamir, and Sharan (2001), and gives a subexponential time parameterized algorithm solving this problem. (via Semantic Scholar)
Sources: Web Of Science, NC State University Libraries, ORCID
Added: August 6, 2018

2015 journal article

Zig-Zag Numberlink is NP-Complete

Journal of Information Processing, 23(3), 239–245.

Contributors: A. Adcock*, E. Demaine*, M. Demaine*, . M.P. O'Brien, F. Reidl*, F. Villaamil*, B. Sullivan n

TL;DR: The 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. (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2014 journal article

An integrated programming and development environment for adiabatic quantum optimization

Computational Science and Discovery, 7(1).

By: T. Humble*, A. McCaskey*, R. Bennink*, J. Billings*, E. Dazevedo*, B. Sullivan*, C. Klymko*, H. Seddiqi*

Contributors: T. Humble*, A. McCaskey*, R. Bennink*, J. Billings*, E. Dazevedo*, B. Sullivan*, C. Klymko*, H. Seddiqi*

TL;DR: An integrated programming and development environment for AQO called Jade Adiabatic Development Environment (JADE) is presented that provides control over all the steps taken during program synthesis and its potential use for benchmarking AQO programs by the quantum computer science community is discussed. (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2014 conference paper

Locally Estimating Core Numbers

Proceedings - IEEE International Conference on Data Mining, ICDM, 2015-January(January), 460–469.

By: M. Obrien n & B. Sullivan n

Contributors: M. Obrien n & B. Sullivan n

TL;DR: A new method for estimating the core number based only on the properties of the graph within a region of radius δ around the vertex is introduced, and an asymptotic error bound of the estimator on random graphs is proved. (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2013 journal article

Adiabatic quantum programming: minor embedding with hard faults

Quantum Information Processing, 13(3), 709–729.

By: C. Klymko*, B. Sullivan n & T. Humble*

Contributors: C. Klymko*, B. Sullivan n & T. Humble*

author keywords: Quantum computing; Adiabatic quantum optimization; Graph embedding; Fault-tolerant computing
TL;DR: Algorithms for embedding arbitrary instances of the adiabatic quantum optimization algorithm into a square lattice of specialized unit cells are presented and are shown to be more resilient to faulty fabrics than naive embedding approaches. (via Semantic Scholar)
Sources: ORCID, Crossref, NC State University Libraries
Added: February 5, 2020

2013 chapter

Evaluating OpenMP Tasking at Scale for the Computation of Graph Hyperbolicity

In OpenMP in the Era of Low Power Devices and Accelerators: Vol. 8122 LNCS (pp. 71–83).

By: A. Adcock*, B. Sullivan*, O. Hernandez* & M. Mahoney*

Contributors: A. Adcock*, B. Sullivan*, O. Hernandez* & M. Mahoney*

TL;DR: It is found that multiple task levels permits finer grained tasks at runtime and results in better performance at scale than worksharing constructs in OpenMP 3.1. (via Semantic Scholar)
UN Sustainable Development Goal Categories
8. Decent Work and Economic Growth (OpenAlex)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020

2013 journal article

On a conjecture of Andrica and Tomescu

Journal of Integer Sequences, 16(3). http://www.scopus.com/inward/record.url?eid=2-s2.0-84880061040&partnerID=MN8TOARS

By: B. Sullivan

Contributors: B. Sullivan

Source: ORCID
Added: August 6, 2022

2013 conference paper

Parallel algorithms for graph optimization using tree decompositions

Proceedings - IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, IPDPSW 2013, 1838–1847.

By: B. Sullivan*, D. Weerapurage* & C. Groer*

Contributors: B. Sullivan*, D. Weerapurage* & C. Groer*

TL;DR: 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. (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2013 conference paper

Tree-Like Structure in Large Social and Information Networks

2013 IEEE 13th International Conference on Data Mining, 1–10.

By: A. Adcock*, B. Sullivan n & M. Mahoney*

Contributors: B. Sullivan n

TL;DR: A detailed empirical analysis of the tree-like properties of realistic informatics graphs is performed using two very different notions of tree-likeness: Gromov's d-hyperbolicity and tree decompositions, tools from structural graph theory which measure how tree- like a graph is in terms of its cut structure. (via Semantic Scholar)
Source: ORCID
Added: August 6, 2022

2011 journal article

A mathematical analysis of the R-MAT random graph generator

Networks, 58(3), 159–170.

By: C. Groër*, B. Sullivan* & S. Poole*

Contributors: C. Groër*, B. Sullivan* & S. Poole*

author keywords: random graph; scale-free graph; R-MAT generator; occupancy problem
TL;DR: This article analyzes the graphs generated by R‐MAT and model the generator in terms of occupancy problems to prove results about the degree distributions of these graphs, and proves that the limiting degree distributions can be expressed as a mixture of normal distributions with means and variances. (via Semantic Scholar)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020

2009 journal article

Counting paths in digraphs

European Journal of Combinatorics, 31(3), 961–975.

By: P. Seymour* & B. Sullivan*

Contributors: P. Seymour* & B. Sullivan*

TL;DR: The problem of bounding the number of (non-induced) 4-vertex paths in 3-free digraphs is studied and an upper bound of 4n^4/75 is shown using Bondy's result for Thomasse's conjecture. (via Semantic Scholar)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020

2008 journal article

Cycles in dense digraphs

Combinatorica, 28(1), 1–18.

By: M. Chudnovsky*, P. Seymour* & B. Sullivan*

Contributors: M. Chudnovsky*, P. Seymour* & B. Sullivan*

TL;DR: It is proved that in general β(G) ≤ γ(G), and that in two special cases: when V (G) is the union of two cliques when the vertices of G can be arranged in a circle such that if distinct u, v, w are in clockwise order and uw is a (directed) edge, then so are both uv, vw. (via Semantic Scholar)
Sources: Crossref, NC State University Libraries, ORCID
Added: February 5, 2020

Employment

Updated: November 5th, 2019 16:58

2019 - present

University of Utah Salt Lake City, UT, US
Associate Professor School of Computing

2013 - 2019

North Carolina State University Raleigh, NC, US
Computer Science

2008 - 2013

Oak Ridge National Laboratory Oak Ridge, TN, US
Computer Science & Mathematics Division

Education

Updated: July 7th, 2016 16:55

2003 - 2008

Princeton University Princeton, NJ, US
PhD Mathematics Mathematics

1999 - 2003

Georgia Institute of Technology Atlanta, GA, US
B.S. Applied Mathematics; B.S. Computer Science

Citation Index includes data from a number of different sources. If you have questions about the sources of data in the Citation Index or need a set of data which is free to re-distribute, please contact us.

Certain data included herein are derived from the Web of Science© and InCites© (2024) of Clarivate Analytics. All rights reserved. You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.