31 citations · 33 across the 4 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2018
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…
cs.DS2018
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…
cs.DS2012★ 1 cited
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…