27 citations · 100 across the 31 of their papers we have counts for
5 papers · 1 filter
Locally Estimating Core Numbers
Michael P. O'Brien, Blair D. Sullivan
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 "cent…
Tree decompositions and social graphs
Aaron B. Adcock, Blair D. Sullivan, Michael W. Mahoney
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…
Zig-Zag Numberlink is NP-Complete
Aaron Adcock, Erik D. Demaine, Martin L. Demaine +4
When can terminal pairs in an grid be connected by vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our ha…
Multi-Level Anomaly Detection on Time-Varying Graph Data
Robert A. Bridges, John Collins, Erik M. Ferragut +2
This work presents a novel modeling and analysis framework for graph sequences which addresses the challenge of detecting and contextualizing anomalies in labelled, streaming graph…
Structural Sparsity of Complex Networks: Bounded Expansion in Random Models and Real-World Graphs
Erik D. Demaine, Felix Reidl, Peter Rossmanith +3
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 effic…