31 citations · 41 across the 9 of their papers we have counts for
9 papers
Red-Blue-Partitioned MST, TSP, and Matching
Matthew P. Johnson
Arkin et al.~\cite{ArkinBCCJKMM17} recently introduced \textit{partitioned pairs} network optimization problems: given a metric-weighted graph on pairs of nodes, the task is to…
Deciding the Closure of Inconsistent Rooted Triples is NP-Complete
Matthew P. Johnson
Interpreting three-leaf binary trees or {\em rooted triples} as constraints yields an entailment relation, whereby binary trees satisfying some rooted triples must also thus satisf…
Selfish Knapsack
Itai Feigenbaum, Matthew P. Johnson
We consider a selfish variant of the knapsack problem. In our version, the items are owned by agents, and each agent can misrepresent the set of items she owns---either by avoiding…
Computing Traversal Times on Dynamic Markovian Paths
Philippe Nain, Don Towsley, Matthew P. Johnson +3
In source routing, a complete path is chosen for a packet to travel from source to destination. While computing the time to traverse such a path may be straightforward in a fixed,…
Secluded Connectivity Problems
Shiri Chechik, M. P. Johnson, Merav Parter +1
Consider a setting where possibly sensitive information sent over a path in a network is visible to every {neighbor} of the path, i.e., every neighbor of some node on the path, thu…
Computing the obstacle number of a plane graph
Matthew P. Johnson, Deniz Sarioz
An obstacle representation of a plane graph G is V(G) together with a set of opaque polygonal obstacles such that G is the visibility graph on V(G) determined by the obstacles. We…