Practical Algorithms for Sparse Graphs.
详细信息
- 作者：Pszona ; Pawel Karol.
- 学历：Ph.D.
- 年：2014
- 毕业院校：University of California
- Department：Information and Computer Science - Ph.D.
- ISBN：9781321021776
- CBH：3627070
- Country：USA
- 语种：English
- FileSize：1409497
- Pages：124
文摘
Practicality of an algorithm is expressed in many different ways. Obvious ones include being fast not just theoretically,but also in practice) or having small memory requirements. Beyond that,a practical algorithm has to be implementable,i.e.,simple enough that one can actually program it. Other aspects of a practical algorithm include its ability to deal with large,real-world data sets and exploiting various characteristics of such data),or producing quality human-usable output. In this dissertation,we discuss all these aspects in detail. Many graphs that appear in practical applications are sparse,meaning that there are few edges compared to the maximum number of edges possible). Different measures have been introduced to capture properties of sparse graphs. We explore them and their interrelations. The main part of this dissertation focuses on two broad areas,connected by the fact that the graphs involved are sparse,and we strive to achieve practical algorithms in all cases. The first one,graph drawing,is concerned with producing high-quality drawings of graphs,so that they are both aesthetically pleasing and meaningful for people to use. The second area focuses on manipulating big data,i.e.,data sets so large that they cannot fit into a single machines memory,rendering many classical algorithms unusable. For the graph drawing part,we start by generalizing a well-known graph drawing paradigm,the arc diagrams,into 3D arc diagrams,with edges drawn as circular arcs. With the goal of achieving good readability in mind,expressed in terms of maximizing angular resolution the minimum angle between adjacent arcs),we introduce several practical algorithms,which in many cases e.g.,for planar graphs) achieve asymptotically optimal angular resolution. The next problem in graph drawing that we approach is maintaining planar drawings of graphs under the ordered streaming model,where the graph arrives edge-by-edge,and the goal is to keep the drawing confined to a polynomial in the number of vertices) area,with as few vertex moves as possible. To achieve this,we revisit the file maintenance problem,and introduce its variant,with bulk relabelings adding the same value to labels of a subset of items stored in the file) allowed. We give algorithms for upward tree drawings,tree-map drawings of trees,and outerplanar graphs. With respect to big data,we focus on handling sparse graphs of bounded degeneracy. Our algorithms work in the external memory model. We start by describing an algorithm for computing approximate degeneracy ordering of a graph,and then use this algorithm as a subroutine in external-memory versions of internal-memory algorithms for solving two problems: finding a cycle of given length and listing all maximal cliques in a graph.