BYU

Abstract by James Scott

Personal Infomation


Presenter's Name

James Scott

Co-Presenters

None

Degree Level

Undergraduate

Co-Authors

None

Abstract Infomation


Department

Mathematics

Faculty Advisor

Robin Roundy

Title

Detecting Decentralized Malware

Abstract

The Fractional Prize-Collecting Steiner Tree Problem (FPCSTP) is NP-Hard in general, but was recently shown to be solvable in worst-case quadratic time on rooted trees. We observe that the algorithm that quickly solves the FPCSTP on rooted trees can be run on a larger class of networks--the "multitrees"--with the same runtime, and that the algorithm cannot terminate with sensible output on a network that is not a multitree. In fact, many dynamic programming algorithms made to run on rooted trees can also run (and terminate with sensible output) on multitrees with no sacrifice of runtime. This is desirable to us since the network on which we wish to solve the FPCSTP is approximately a multitree. With that in mind, have developed an algorithm that finds a maximal spanning multitree in an arbitrary DAG (directed acyclic graph). We will discuss an application involving detection of malware distributed among several files in a computer.