Graph factorization and pseudofactorization with applications to hypercube embeddings

In many contexts, it is useful to determine if a particular distance metric can be broken down into other metrics about which more is known. In particular, if a metric can be embedded into a hypercube, the plethora of preexisting knowledge about the structure of a hypercube can provide knowledge about the structure in question. In this paper, we examine the concepts of graph factorization and pseudofactorization, in which a graph is broken up into smaller graphs whose Cartesian product it is isomorphic to or is an isometric subgraph of, respectively. We show that the same or slightly modified versions of the techniques used for this process in the context of unweighted graphs also work for weighted graphs. While it is NP-hard to decide if a general distance metric is hypercube embeddable, we also discuss how these results expand the number of known types of graphs and distance metrics for which this problem is polynomial time decidable. We also discuss why this kind of decomposition of graphs and distance metrics may be of interest in a variety of fields.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Sheridan, Kristin

Advisors dc:contributor.advisor

• Williams, Virginia Vassilevska
• Bathe, Mark

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/139112

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/139112