東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

An empirical study of expander graph...

Lotts, Mark Allen.

Linked to FindBook

Google Book

Amazon

博客來

An empirical study of expander graphs and graph expansion.

Record Type:	Electronic resources : Monograph/item
Title/Author:	An empirical study of expander graphs and graph expansion./
Author:	Lotts, Mark Allen.
Description:	153 p.
Notes:	Source: Masters Abstracts International, Volume: 55-05.
Contained By:	Masters Abstracts International55-05(E).
Subject:	Computer science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10140598
ISBN:	9781339959955

An empirical study of expander graphs and graph expansion.
Lotts, Mark Allen.

An empirical study of expander graphs and graph expansion. - 153 p.

Source: Masters Abstracts International, Volume: 55-05.

Thesis (M.S.)--University of Maryland, Baltimore County, 2016.

Expander graphs are commonly studied objects in computer science and mathematics that are found in the proofs of many important theorems. The vast majority of these theoretical uses of expanders rely on probabilistic statements of existence and do not grapple with the challenge of creating expander graphs or validating their expansion properties. In this paper, we will define expander graphs and describe different ways their expansion can be measured. We will discuss applications of expander graphs and provide empirical evidence of how they can be used in practice. We will also outline the difficulties of computing exact expansion rates and the hardness of estimating these rates, relating these problems to well-known results and conjectures in complexity theory. Using our own implementation of graph creation and verification algorithms, we will gain an empirical understanding of expander graphs, utilizing high-performance computing resources and repurposing well-known statistical methods to analyze expansion. We will show that, given an arbitrary graph, its potential to be used as an expander can be measured and bounded by employing community detection algorithms that seek to maximize modularity.

ISBN: 9781339959955Subjects--Topical Terms:

523869
Computer science.

An empirical study of expander graphs and graph expansion.
LDR:02060nmm a2200277 4500 001 2079191
005 20161210083248.5
008 170521s2016 ||||||||||||||||| ||eng d
020 $a 9781339959955
035 $a (MiAaPQ)AAI10140598
035 $a AAI10140598
040 $a MiAaPQ $c MiAaPQ
100 1 $a Lotts, Mark Allen. $3 3194854
245 1 3 $a An empirical study of expander graphs and graph expansion.
300 $a 153 p.
500 $a Source: Masters Abstracts International, Volume: 55-05.
500 $a Adviser: Richard Chang.
502 $a Thesis (M.S.)--University of Maryland, Baltimore County, 2016.
520 $a Expander graphs are commonly studied objects in computer science and mathematics that are found in the proofs of many important theorems. The vast majority of these theoretical uses of expanders rely on probabilistic statements of existence and do not grapple with the challenge of creating expander graphs or validating their expansion properties. In this paper, we will define expander graphs and describe different ways their expansion can be measured. We will discuss applications of expander graphs and provide empirical evidence of how they can be used in practice. We will also outline the difficulties of computing exact expansion rates and the hardness of estimating these rates, relating these problems to well-known results and conjectures in complexity theory. Using our own implementation of graph creation and verification algorithms, we will gain an empirical understanding of expander graphs, utilizing high-performance computing resources and repurposing well-known statistical methods to analyze expansion. We will show that, given an arbitrary graph, its potential to be used as an expander can be measured and bounded by employing community detection algorithms that seek to maximize modularity.
590 $a School code: 0434.
650 4 $a Computer science. $3 523869
650 4 $a Theoretical mathematics. $3 3173530
690 $a 0984
690 $a 0642
710 2 $a University of Maryland, Baltimore County. $b Computer Science. $3 1018441
773 0 $t Masters Abstracts International $g 55-05(E).
790 $a 0434
791 $a M.S.
792 $a 2016
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10140598