Planar Separators
computer science crazy Super Moderator Posts: 3,048 Joined: Dec 2008 
08042009, 07:40 AM
Introduction I/Oefficient graph algorithms have received considerable attention lately because massive graphs arise naturally in many applications. Recent web crawls, for example, produce graphs of on the order of 200 million nodes and 2 billion edges. Recent work in web modeling uses depthfirst search, breadthfirst search, shortest paths, and connected components as primitive operations for investigating the structure of the web. Massive graphs are also often manipulated in Geographic Information Systems (GIS), where many fundamental problems can be formulated as basic graph problems. The graphs arising in GIS applications are often planar. Yet another example of massive graphs is AT&T's 20TB phone call graph [9]. When working with such large data sets, the transfer of data between internal and external memory, and not the internal memory computation, is often the bottleneck. Thus, I/Oefficient algorithms can lead to considerable runtime improvements. Breadthfirst search (BFS) and depthfirst search (DFS) are the two most fundamental graphsearching strategies. They are extensively used in internal memory algorithms, as they are easy to perform in linear time; yet they provide valuable information about the structure of the given graph. Unfortunately, no I/Oefficient algorithms for BFS and DFS in arbitrary sparse graphs are known, while existing algorithms perform reasonably well on dense graphs. Together with recent results on singlesource shortest paths (SSSP) and DFS, our algorithm leads to I/Oefficient algorithms for SSSP, BFS, and DFS on undirected embedded planar graphs. Model of Computation The algorithms in this paper are designed and analyzed in the Parallel Disk Model (PDM). In thismodel, D identical disks of unlimited size are attached to a machine with an internal memory capable of holding M data items. These disks constitute the external memory of the machine. Initially, all data is stored on disk. Each disk is partitioned into blocks of B data items each. An I/Ooperation is the transfer of up to D blocks, at most one per disk, to or from internal memory from or to external memory. The complexity of an algorithm in the PDM is the number of I/Ooperations it performs. Sorting, permuting, and scanning an array of N consecutive data items are primitive operations often used in external memory algorithms. Their I/Ocomplexities are sort(N) = Q((N=DB) logM=B(N=B)), perm(N) = Q(min(N; sort(N))), and scan(N) = O(N=DB), respectively. Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion




Important Note..!
If you are not satisfied with above reply ,..PleaseASK HERE
So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this pagePossibly Related Threads...  
Thread  Author  Replies  Views  Last Post  
Graph Separators  computer science crazy  0  1,354 
22092008, 10:12 AM Last Post: computer science crazy 

Planar Separators  computer science crazy  0  1,149 
22092008, 10:02 AM Last Post: computer science crazy 