NDLI: General spanning trees and reachability query evaluation

Please wait, while we are loading the content...

CINDI: a digital library for academics

Anonymizing location-based RFID data

Agile development: issues and avenues requiring a substantial enhancement of the business perspective in large projects

A type system for hybrid intensional-imperative programming support in GIPSY

Markovian workload modeling for Enterprise Application Servers

CPU, SMP and GPU implementations of Nohalo level 1, a fast co-convex antialiasing image resampler

An automated procedure for identifying poorly documented object oriented software components

A local algorithm for dominating sets of quasi-unit disk graphs

Broadcasting in necklace graphs

An adaptive multi-strategy approach for semantic mapping

The promise of solid state disks: increasing efficiency and reducing cost of DBMS processing

Bridging the gap: Discrete-Event Systems for software engineering (short position paper)

A verification framework for access control in dynamic web applications

Radius selection algorithms for sphere decoding

Texture map: an effective representation for image segmentation

Edit metric decoding: a new hope

Impediments to general purpose Content Based Image search

Issues in pattern mining and their resolutions

XPath query evaluation based on the stack encoding

Integrating heterogeneous user interfaces in service oriented web applications

ACDL: a communication choreography for discrete step multi-agent social simulations

Autonomic specification of self-protection for distributed MARF with ASSL

Use of semantic web technology for adding 3D detail to GIS landscape data

General spanning trees and reachability query evaluation

Option pricing using Particle Swarm Optimization

Network survivability in large-scale regional failure scenarios

An ASSL-generated architecture for autonomic systems

Application of advanced rendering and animation techniques for 3D games to softbody modeling and animation

Component placement and location for a dynamic software composition system

Designing an interactive OpenGL slide-based presentation of the softbody simulation system for teaching and learning of computer graphics techniques

Integrating usability engineering and software engineering in mixed reality system development

Modeling for dynamic aspect-oriented development

Real-time haptic display of fluids

ConfSys2: an improved web-based multi-conference management system

General spanning trees and reachability query evaluation

Content Provider	ACM Digital Library
Author	Chen, Yangjun
Abstract	Graph reachability is fundamental to a wide range of applications, including CAD/CAM, CASE, office systems, software management, as well as geographical navigation and internet routing. Many applications involve huge graphs and requires fast answering of reachability queries. Several reachability labeling methods have been proposed for this purpose. They assign labels to the nodes, such that the reachability between any two nodes can be determined using their labels only. In this paper, we propose a new data structure, called a general spanning tree of a directed acyclic graph (DAG) to minimize label space. Different from a traditional spanning tree, an edge in a general spanning tree T of a DAG G may corresponds to a path in G. That is, for each edge u → v in T, we have a path from u to v in G. An algorithm is discussed to find such a tree with the least number of leaf nodes in O(bn √b) time, where n is the number of the nodes of G, and b is the number of the leaf nodes of T. It can be proven that b equals G's width, defined to be the size of a largest node subset U of G such that for every pair of nodes u, v ∈ U, there does not exist a path from u to v or from v to u. Based on T, we are able to reduce the label space to O(bn) with O(logb) reachability query time. Our method can also be extended for graphs containing cycles.
Starting Page	243
Ending Page	252
Page Count	10
File Format	PDF
ISBN	9781605584010
DOI	10.1145/1557626.1557665
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-05-19
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Decomposing DAGs into spanning trees: A new way to compress transitive closures

Efficient reachability query evaluation in large spatiotemporal contact datasets.

Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets

Privacy-Preserving Reachability Query Services for Massive Networks

Spanning Trees with Many Leaves

Computing minimum spanning trees efficiently

K-reach: Who is in your small world

Embedding Spanning Trees in Random Graphs

Optimum Communication Spanning Trees

General spanning trees and reachability query evaluation

Similar Documents

Decomposing DAGs into spanning trees: A new way to compress transitive closures

Efficient reachability query evaluation in large spatiotemporal contact datasets.

Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets

Privacy-Preserving Reachability Query Services for Massive Networks

Spanning Trees with Many Leaves

Computing minimum spanning trees efficiently

K-reach: Who is in your small world

Embedding Spanning Trees in Random Graphs

Optimum Communication Spanning Trees

General spanning trees and reachability query evaluation