52 citations · 107 across the 10 of their papers we have counts for
6 papers · 1 filter
ERGMs are Hard
Michael J. Bannister, William E. Devanny, David Eppstein
We investigate the computational complexity of the exponential random graph model (ERGM) commonly used in social network analysis. This model represents a probability distribution…
Windows into Geometric Events: Data Structures for Time-Windowed Querying of Temporal Point Sets
Michael J. Bannister, William E. Devanny, Michael T. Goodrich +2
We study geometric data structures for sets of point-based temporal events, answering time-windowed queries, i.e., given a contiguous time interval we answer common geometric queri…
Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
Michael J. Bannister, David Eppstein
We investigate crossing minimization for 1-page and 2-page book drawings. We show that computing the 1-page crossing number is fixed-parameter tractable with respect to the number…
Parameterized Complexity of 1-Planarity
Michael J. Bannister, Sergio Cabello, David Eppstein
We consider the problem of finding a 1-planar drawing for a general graph, where a 1-planar drawing is a drawing in which each edge participates in at most one crossing. Since this…
Windows into Relational Events: Data Structures for Contiguous Subsequences of Edges
Michael J. Bannister, Christopher DuBois, David Eppstein +1
We consider the problem of analyzing social network data sets in which the edges of the network have timestamps, and we wish to analyze the subgraphs formed from edges in contiguou…
Randomized Speedup of the Bellman-Ford Algorithm
Michael J. Bannister, David Eppstein
We describe a variant of the Bellman-Ford algorithm for single-source shortest paths in graphs with negative edges but no negative cycles that randomly permutes the vertices and us…