@article {17673,
	title = {Mobile Data Offloading through Opportunistic Communications and Social Participation},
	journal = {Mobile Computing, IEEE Transactions on},
	volume = {11},
	year = {2012},
	month = {2012/05//},
	pages = {821 - 834},
	abstract = {3G networks are currently overloaded, due to the increasing popularity of various applications for smartphones. Offloading mobile data traffic through opportunistic communications is a promising solution to partially solve this problem, because there is almost no monetary cost for it. We propose to exploit opportunistic communications to facilitate information dissemination in the emerging Mobile Social Networks (MoSoNets) and thus reduce the amount of mobile data traffic. As a case study, we investigate the target-set selection problem for information delivery. In particular, we study how to select the target set with only k users, such that we can minimize the mobile data traffic over cellular networks. We propose three algorithms, called Greedy, Heuristic, and Random, for this problem and evaluate their performance through an extensive trace-driven simulation study. Our simulation results verify the efficiency of these algorithms for both synthetic and real-world mobility traces. For example, the Heuristic algorithm can offload mobile data traffic by up to 73.66 percent for a real-world mobility trace. Moreover, to investigate the feasibility of opportunistic communications for mobile phones, we implement a proof-of-concept prototype, called Opp-off, on Nokia N900 smartphones, which utilizes their Bluetooth interface for device/service discovery and content transfer.},
	keywords = {3G mobile communication, 3G networks, Bluetooth interface, cellular networks, cellular radio, content transfer, device/service discovery, graph theory, greedy algorithm, heuristic algorithm, information delivery, information dissemination, mobile data offloading, mobile data traffic, mobile phones, mobile social networks, MoSoNets, Nokia N900 smartphones, Opp-off, opportunistic communications, random algorithm, real-world mobility traces, smart phones, social networking (online), social participation, target-set selection problem, telecommunication network routing, Telecommunication traffic, trace-driven simulation study},
	isbn = {1536-1233},
	doi = {10.1109/TMC.2011.101},
	author = {Han,Bo and Hui,Pan and Kumar,V. S.A and Marathe,M. V and Shao,Jianhua and Srinivasan, Aravind}
}
@conference {12450,
	title = {Entropy rate superpixel segmentation},
	booktitle = {2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
	year = {2011},
	month = {2011/06/20/25},
	pages = {2097 - 2104},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We propose a new objective function for superpixel segmentation. This objective function consists of two components: entropy rate of a random walk on a graph and a balancing term. The entropy rate favors formation of compact and homogeneous clusters, while the balancing function encourages clusters with similar sizes. We present a novel graph construction for images and show that this construction induces a matroid - a combinatorial structure that generalizes the concept of linear independence in vector spaces. The segmentation is then given by the graph topology that maximizes the objective function under the matroid constraint. By exploiting submodular and mono-tonic properties of the objective function, we develop an efficient greedy algorithm. Furthermore, we prove an approximation bound of {\textonehalf} for the optimality of the solution. Extensive experiments on the Berkeley segmentation benchmark show that the proposed algorithm outperforms the state of the art in all the standard evaluation metrics.},
	keywords = {balancing function, Berkeley segmentation benchmark, Complexity theory, Entropy, entropy rate, graph construction, graph theory, graph topology, greedy algorithm, Greedy algorithms, homogeneous clusters, Image edge detection, Image segmentation, matrix algebra, matroid constraint, measurement, pattern clustering, Random variables, standard evaluation metrics, superpixel segmentation, vector spaces},
	isbn = {978-1-4577-0394-2},
	doi = {10.1109/CVPR.2011.5995323},
	author = {Ming-Yu Liu and Tuzel, O. and Ramalingam, S. and Chellapa, Rama}
}
@conference {17181,
	title = {Group-in-a-Box Layout for Multi-faceted Analysis of Communities},
	booktitle = {Privacy, Security, Risk and Trust (PASSAT), 2011 IEEE Third International Conference on and 2011 IEEE Third International Confernece on Social Computing (SocialCom)},
	year = {2011},
	month = {2011/10/09/11},
	pages = {354 - 361},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Communities in social networks emerge from interactions among individuals and can be analyzed through a combination of clustering and graph layout algorithms. These approaches result in 2D or 3D visualizations of clustered graphs, with groups of vertices representing individuals that form a community. However, in many instances the vertices have attributes that divide individuals into distinct categories such as gender, profession, geographic location, and similar. It is often important to investigate what categories of individuals comprise each community and vice-versa, how the community structures associate the individuals from the same category. Currently, there are no effective methods for analyzing both the community structure and the category-based partitions of social graphs. We propose Group-In-a-Box (GIB), a meta-layout for clustered graphs that enables multi-faceted analysis of networks. It uses the tree map space filling technique to display each graph cluster or category group within its own box, sized according to the number of vertices therein. GIB optimizes visualization of the network sub-graphs, providing a semantic substrate for category-based and cluster-based partitions of social graphs. We illustrate the application of GIB to multi-faceted analysis of real social networks and discuss desirable properties of GIB using synthetic datasets.},
	keywords = {Algorithm design and analysis, category based social graph partitions, clustered graphs, clustering, Clustering algorithms, Communities, data visualisation, force-directed, gender, geographic location, graph layout algorithms, graph theory, group-in-a-box, group-in-a-box layout, Image edge detection, Layout, meta-layout, multifaceted community analysis, network subgraph visualization, network visualization, pattern clustering, profession, semantic substrates, Social network services, social networking (online), social networks, treemap space filling technique, Visualization},
	isbn = {978-1-4577-1931-8},
	doi = {10.1109/PASSAT/SocialCom.2011.139},
	author = {Rodrigues,E.M. and Milic-Frayling,N. and Smith,M. and Shneiderman, Ben and Hansen,D.}
}
@conference {19035,
	title = {Link prediction by de-anonymization: How We Won the Kaggle Social Network Challenge},
	year = {2011},
	month = {2011},
	pages = {1825 - 1834},
	abstract = {This paper describes the winning entry to the IJCNN 2011 Social Network Challenge run by Kaggle.com. The goal of the contest was to promote research on real-world link prediction, and the dataset was a graph obtained by crawling the popular Flickr social photo sharing website, with user identities scrubbed. By de-anonymizing much of the competition test set using our own Flickr crawl, we were able to effectively game the competition. Our attack represents a new application of de-anonymization to gaming machine learning contests, suggesting changes in how future competitions should be run. We introduce a new simulated annealing-based weighted graph matching algorithm for the seeding step of de-anonymization. We also show how to combine de-anonymization with link prediction-the latter is required to achieve good performance on the portion of the test set not de-anonymized-for example by training the predictor on the de-anonymized portion of the test set, and combining probabilistic predictions from de-anonymization and link prediction.},
	keywords = {deanonymization, Flickr social photo sharing Website, graph theory, IJCNN 2011 social network challenge, Kaggle social network challenge, learning (artificial intelligence), machine learning, realworld link prediction, Simulated annealing, simulated annealing-based weighted graph matching algorithm, social networking (online)},
	author = {Narayanan, A. and Elaine Shi and Rubinstein, B.I.P.}
}
@conference {17643,
	title = {Predicting Trust and Distrust in Social Networks},
	booktitle = {Privacy, Security, Risk and Trust (PASSAT), 2011 IEEE Third International Conference on and 2011 IEEE Third International Confernece on Social Computing (SocialCom)},
	year = {2011},
	month = {2011/10/09/11},
	pages = {418 - 424},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {As user-generated content and interactions have overtaken the web as the default mode of use, questions of whom and what to trust have become increasingly important. Fortunately, online social networks and social media have made it easy for users to indicate whom they trust and whom they do not. However, this does not solve the problem since each user is only likely to know a tiny fraction of other users, we must have methods for inferring trust - and distrust - between users who do not know one another. In this paper, we present a new method for computing both trust and distrust (i.e., positive and negative trust). We do this by combining an inference algorithm that relies on a probabilistic interpretation of trust based on random graphs with a modified spring-embedding algorithm. Our algorithm correctly classifies hidden trust edges as positive or negative with high accuracy. These results are useful in a wide range of social web applications where trust is important to user behavior and satisfaction.},
	keywords = {distrust prediction, Electronic publishing, Encyclopedias, graph theory, inference algorithm, Inference algorithms, inference mechanisms, Internet, negative trust, online social networks, positive trust, Prediction algorithms, probability, random graphs, security of data, social media, social networking (online), spring-embedding algorithm, Training, trust inference, trust probabilistic interpretation, user behavior, user satisfaction, user-generated content, user-generated interactions},
	isbn = {978-1-4577-1931-8},
	doi = {10.1109/PASSAT/SocialCom.2011.56},
	author = {DuBois,T. and Golbeck,J. and Srinivasan, Aravind}
}
@article {17487,
	title = {Visual Exploration across Biomedical Databases},
	journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
	volume = {8},
	year = {2011},
	month = {2011/04//March},
	pages = {536 - 550},
	abstract = {Though biomedical research often draws on knowledge from a wide variety of fields, few visualization methods for biomedical data incorporate meaningful cross-database exploration. A new approach is offered for visualizing and exploring a query-based subset of multiple heterogeneous biomedical databases. Databases are modeled as an entity-relation graph containing nodes (database records) and links (relationships between records). Users specify a keyword search string to retrieve an initial set of nodes, and then explore intra- and interdatabase links. Results are visualized with user-defined semantic substrates to take advantage of the rich set of attributes usually present in biomedical data. Comments from domain experts indicate that this visualization method is potentially advantageous for biomedical knowledge exploration.},
	keywords = {Bioinformatics, Biomedical computing, biomedical databases, cross-database exploration, Data exploration and discovery, Data visualization, database management systems, Databases, Factual, DNA, graph theory, Information Storage and Retrieval, information visualization., Keyword search, medical computing, natural language processing, Proteins, semantic networks, semantics, sequences, text mining, User-Computer Interface, user-defined semantics, visual databases},
	isbn = {1545-5963},
	doi = {10.1109/TCBB.2010.1},
	author = {Lieberman,M.D. and Taheri, S. and Guo,Huimin and Mirrashed,F. and Yahav,I. and Aris,A. and Shneiderman, Ben}
}
@conference {16470,
	title = {ApproxRank: Estimating Rank for a Subgraph},
	booktitle = {IEEE 25th International Conference on Data Engineering, 2009. ICDE {\textquoteright}09},
	year = {2009},
	month = {2009/04/29/March},
	pages = {54 - 65},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Customized semantic query answering, personalized search, focused crawlers and localized search engines frequently focus on ranking the pages contained within a subgraph of the global Web graph. The challenge for these applications is to compute PageRank-style scores efficiently on the subgraph, i.e., the ranking must reflect the global link structure of the Web graph but it must do so without paying the high overhead associated with a global computation. We propose a framework of an exact solution and an approximate solution for computing ranking on a subgraph. The IdealRank algorithm is an exact solution with the assumption that the scores of external pages are known. We prove that the IdealRank scores for pages in the subgraph converge. Since the PageRank-style scores of external pages may not typically be available, we propose the ApproxRank algorithm to estimate scores for the subgraph. Both IdealRank and ApproxRank represent the set of external pages with an external node L1 and extend the subgraph with links to L1. They also modify the PageRank-style transition matrix with respect to L1. We analyze the L1 distance between IdealRank scores and ApproxRank scores of the subgraph and show that it is within a constant factor of the L1 distance of the external pages (e.g., the true PageRank scores and uniform scores assumed by ApproxRank). We compare ApproxRank and a stochastic complementation approach (SC), a current best solution for this problem, on different types of subgraphs. ApproxRank has similar or superior performance to SC and typically improves on the runtime performance of SC by an order of magnitude or better. We demonstrate that ApproxRank provides a good approximation to PageRank for a variety of subgraphs.},
	keywords = {Application software, ApproxRank, Computer applications, Crawlers, customized semantic query answering, Data engineering, Educational institutions, Explosions, focused crawlers, global Web graph, graph theory, IdealRank algorithm, Internet, localized search engines, PageRank-style, personalized search, Query processing, Runtime, Search engines, Stochastic processes, Web pages},
	isbn = {978-1-4244-3422-0},
	doi = {10.1109/ICDE.2009.108},
	author = {Yao Wu and Raschid, Louiqa}
}
@conference {17559,
	title = {Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints},
	booktitle = {IEEE INFOCOM 2008. The 27th Conference on Computer Communications},
	year = {2008},
	month = {2008/04/13/18},
	pages = {1166 - 1174},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {A fundamental problem in wireless networks is to estimate its throughput capacity - given a set of wireless nodes, and a set of connections, what is the maximum rate at which data can be sent on these connections. Most of the research in this direction has focused on either random distributions of points, or has assumed simple graph-based models for wireless interference. In this paper, we study capacity estimation problem using the more general Signal to Interference Plus Noise Ratio (SINR) model for interference, on arbitrary wireless networks. The problem becomes much harder in this setting, because of the non-locality of the SINR model. Recent work by Moscibroda et al. (2006) has shown that the throughput in this model can differ from graph based models significantly. We develop polynomial time algorithms to provably approximate the total throughput in this setting.},
	keywords = {Algorithm design and analysis, approximation algorithm, Approximation algorithms, approximation theory, Computer networks, Computer science, graph theory, graph-based model, Interference constraints, polynomial time algorithm, Propagation losses, Protocols, radio networks, radiofrequency interference, signal to interference plus noise ratio, Signal to noise ratio, Throughput, wireless interference, wireless network, Wireless networks},
	isbn = {978-1-4244-2025-4},
	doi = {10.1109/INFOCOM.2008.172},
	author = {Chafekar,D. and Kumart,V. S.A and Marathe,M. V and Parthasarathy,S. and Srinivasan, Aravind}
}
@article {12544,
	title = {Model Driven Segmentation of Articulating Humans in Laplacian Eigenspace},
	journal = {Pattern Analysis and Machine Intelligence, IEEE Transactions on},
	volume = {30},
	year = {2008},
	month = {2008/10//},
	pages = {1771 - 1785},
	abstract = {We propose a general approach using Laplacian Eigenmaps and a graphical model of the human body to segment 3D voxel data of humans into different articulated chains. In the bottom-up stage, the voxels are transformed into a high-dimensional (6D or less) Laplacian Eigenspace (LE) of the voxel neighborhood graph. We show that LE is effective at mapping voxels on long articulated chains to nodes on smooth 1D curves that can be easily discriminated, and prove these properties using representative graphs. We fit 1D splines to voxels belonging to different articulated chains such as the limbs, head and trunk, and determine the boundary between splines using the spline fitting error. A top-down probabilistic approach is then used to register the segmented chains, utilizing their mutual connectivity and individual properties. Our approach enables us to deal with complex poses such as those where the limbs form loops. We use the segmentation results to automatically estimate the human body models. While we use human subjects in our experiments, the method is fairly general and can be applied to voxel-based segmentation of any articulated object composed of long chains. We present results on real and synthetic data that illustrate the usefulness of this approach.},
	keywords = {3D voxel data segmentation, algorithms, Anatomic;Pattern Recognition, Artificial intelligence, Automated;Reproducibility of Results;Sensitivity and Specificity;Whole Body Imaging;, Computer simulation, Computer-Assisted;Imaging, curve fitting, Eigenvalues and eigenfunctions, graph theory, human articulation, human body graphical model, human motion analysis, HUMANS, Image Enhancement, Image Interpretation, Image motion analysis, image registration, Image segmentation, Laplace transforms, Laplacian eigenspace transform, model driven segmentation, probability, representative graph, skeleton registration, Smoothing methods, solid modelling, spline fitting error, splines (mathematics), Three-Dimensional;Joints;Models, top-down probabilistic approach, voxel neighborhood graph},
	isbn = {0162-8828},
	doi = {10.1109/TPAMI.2007.70823},
	author = {Sundaresan, A. and Chellapa, Rama}
}
@conference {15271,
	title = {Uncovering Genomic Reassortments among Influenza Strains by Enumerating Maximal Bicliques},
	booktitle = {IEEE International Conference on Bioinformatics and Biomedicine, 2008. BIBM {\textquoteright}08},
	year = {2008},
	month = {2008/11/03/5},
	pages = {223 - 230},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {The evolutionary histories of viral genomes have received significant recent attention due to their importance in understanding virulence and the corresponding ramifications to public health. We present a novel framework to detect reassortment events in influenza based on the comparison of two distributions of phylogenetic trees, rather than a pair of, possibly unreliable, consensus trees. We show how to detect all high-probability inconsistencies between two distributions of trees by enumerating maximal bicliques within a defined incompatibility graph. In the process, we give the first quadratic delay algorithm for enumerating maximal bicliques within general bipartite graphs. We demonstrate the utility of our approach by applying it to several sets of influenza genomes (both human- and avian-hosted) and successfully identify all known reassortment events and a few novel candidate reassortments. In addition, on simulated datasets, our approach correctly finds implanted reassortments and rarely detects reassortments where none were introduced.},
	keywords = {avian hosted influenza genome, Bioinformatics, Capacitive sensors, Delay, diseases, Event detection, general bipartite graphs, genomic reassortments, Genomics, graph theory, high probability inconsistencies, History, human hosted influenza genome, incompatibility graph, Influenza, influenza strain, maximal biclique, maximal biclique enumeration, microorganisms, phylogenetic trees, Phylogeny, Public healthcare, quadratic delay algorithm, reassortment, reassortment event detection, Tree graphs, viral genome evolutionary history, virulence},
	isbn = {978-0-7695-3452-7},
	doi = {10.1109/BIBM.2008.78},
	author = {Nagarajan,N. and Kingsford, Carl}
}
@article {16983,
	title = {Balancing Systematic and Flexible Exploration of Social Networks},
	journal = {IEEE Transactions on Visualization and Computer Graphics},
	volume = {12},
	year = {2006},
	month = {2006/10//Sept},
	pages = {693 - 700},
	abstract = {Social network analysis (SNA) has emerged as a powerful method for understanding the importance of relationships in networks. However, interactive exploration of networks is currently challenging because: (1) it is difficult to find patterns and comprehend the structure of networks with many nodes and links, and (2) current systems are often a medley of statistical methods and overwhelming visual output which leaves many analysts uncertain about how to explore in an orderly manner. This results in exploration that is largely opportunistic. Our contributions are techniques to help structural analysts understand social networks more effectively. We present SocialAction, a system that uses attribute ranking and coordinated views to help users systematically examine numerous SNA measures. Users can (1) flexibly iterate through visualizations of measures to gain an overview, filter nodes, and find outliers, (2) aggregate networks using link structure, find cohesive subgroups, and focus on communities of interest, and (3) untangle networks by viewing different link types separately, or find patterns across different link types using a matrix overview. For each operation, a stable node layout is maintained in the network visualization so users can make comparisons. SocialAction offers analysts a strategy beyond opportunism, as it provides systematic, yet flexible, techniques for exploring social networks},
	keywords = {Aggregates, algorithms, attribute ranking, Cluster Analysis, Computer Graphics, Computer simulation, Coordinate measuring machines, coordinated views, Data analysis, data visualisation, Data visualization, exploratory data analysis, Filters, Gain measurement, graph theory, Graphical user interfaces, Information Storage and Retrieval, interactive graph visualization, matrix algebra, matrix overview, Models, Biological, Navigation, network visualization, Pattern analysis, Population Dynamics, Social Behavior, social network analysis, Social network services, social networks, social sciences computing, Social Support, SocialAction, software, statistical analysis, statistical methods, User-Computer Interface},
	isbn = {1077-2626},
	doi = {10.1109/TVCG.2006.122},
	author = {Perer,A. and Shneiderman, Ben}
}
@article {13260,
	title = {A Dimension-Independent Representation for Multiresolution Nonmanifold Meshes},
	journal = {Journal of Computing and Information Science in Engineering},
	volume = {6},
	year = {2006},
	month = {2006///},
	pages = {397 - 404},
	abstract = {We consider the problem of representing and manipulating nonmanifold objects of any dimension and at multiple resolutions. We present a modeling scheme based on (1) a multiresolution representation, called the vertex-based nonmanifold multitessellation, (2) a compact and dimension-independent data structure, called the Simplified Incidence Graph (SIG), and (3) an atomic mesh update operator, called vertex-pair contraction/vertex expansion. We propose efficient algorithms for performing the vertex-pair contraction on a simplicial mesh encoded as a SIG, and an effective representation for encoding this multiresolution model based on a compact encoding of vertex-pair contractions and vertex expansions.},
	keywords = {computational geometry, graph theory, mesh generation},
	doi = {10.1115/1.2364207},
	url = {http://link.aip.org/link/?CIS/6/397/1},
	author = {De Floriani, Leila and Hui,Annie}
}
@conference {12391,
	title = {Mapping Multimedia Applications Onto Configurable Hardware With Parameterized Cyclo-Static Dataflow Graphs},
	booktitle = {Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on},
	volume = {3},
	year = {2006},
	month = {2006/05//},
	pages = {III - III},
	abstract = {This paper develops methods for model-based design and implementation of image processing applications. We apply our previously developed meta-modeling technique of homogeneous parameterized dataflow (HPDF) (M. Sen et al., 2005) to the framework of cyclostatic dataflow (CSDF) (G. Bilsen et al., 1996), and demonstrate this integrated modeling methodology through hardware mapping of a gesture recognition application. We also provide a comparative study between HPDF/CSDF-based representation of the gesture recognition application, and a previously developed version based on applying HPDF in conjunction with conventional synchronous dataflow (SDF) semantics (M. Sen et al., 2005)},
	keywords = {configurable hardware, Data communication, Gesture recognition, gesture recognition application, graph theory, hardware mapping, image processing applications, mapping multimedia applications, meta-modeling technique, model-based design, Multimedia communication, parameterized cyclo-static dataflow graphs},
	doi = {10.1109/ICASSP.2006.1660838},
	author = {Haim,F. and Sen,M. and Ko,Dong-Ik and Bhattacharyya, Shuvra S. and Wolf,W.}
}
@conference {12388,
	title = {CASPER: an integrated energy-driven approach for task graph scheduling on distributed embedded systems},
	booktitle = {Application-Specific Systems, Architecture Processors, 2005. ASAP 2005. 16th IEEE International Conference on},
	year = {2005},
	month = {2005/07//},
	pages = {191 - 197},
	abstract = {For multiprocessor embedded systems, the dynamic voltage scaling (DVS) technique can be applied to scheduled applications for energy reduction. DVS utilizes slack in the schedule to slow down processes and save energy. Therefore, it is generally believed that the maximal energy saving is achieved on a schedule with the minimum makespan (maximal slack). Most current approaches treat task assignment, scheduling, and DVS separately. In this paper, we present a framework called CASPER (combined assignment, scheduling, and power-management) that challenges this common belief by integrating task scheduling and DVS under a single iterative optimization loop via genetic algorithm. We have conducted extensive experiments to validate the energy efficiency of CASPER. For homogeneous multiprocessor systems (in which all processors are of the same type), we consider a recently proposed slack distribution algorithm (PDP-SPM) by S. Hua and G. Qu (2005): applying PDP-SPM on the schedule with the minimal makespan gives an average of 53.8\% energy saving; CASPER finds schedules with slightly larger makespan but a 57.3\% energy saving, a 7.8\% improvement. For heterogeneous systems, we consider the power variation DVS (PV-DVS) algorithm by Schmitz et al. (2004), CASPER improves its energy efficiency by 8.2\%. Finally, our results also show that the proposed single loop CASPER framework saves 23.3\% more energy over GMA+EE-GLSA by Schmitz et al. (2002), the only other known integrated approach with a nested loop that combines scheduling and power management in the inner loop but leaves assignment in the outer loop.},
	keywords = {CASPER, combined-assignment-scheduling-and-power-management, computational complexity, distributed system, dynamic voltage scaling, embedded systems, energy reduction, genetic algorithm, Genetic algorithms, graph theory, homogeneous multiprocessor system, maximal energy saving, Multiprocessing systems, multiprocessor embedded system, optimization loop, power management, power variation, Processor scheduling, slack distribution algorithm, task assignment, task graph scheduling},
	doi = {10.1109/ASAP.2005.23},
	author = {Kianzad,V. and Bhattacharyya, Shuvra S. and Gang Qu}
}
@conference {15690,
	title = {Automatic video summarization for wireless and mobile environments},
	booktitle = {2004 IEEE International Conference on Communications},
	volume = {3},
	year = {2004},
	month = {2004/06/20/24},
	pages = {1532- 1536 Vol.3 - 1532- 1536 Vol.3},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {In this paper, we propose a novel video summarization technique using which we can automatically generate high quality video summaries suitable for wireless and mobile environments. The significant contribution of this paper lies in the proposed clustering scheme. We use Delaunay diagrams to cluster multidimensional point data corresponding to the frame contents of the video. In contrast to the existing clustering techniques used for summarization, our clustering algorithm is fully automatic and well suited for batch processing. We illustrate the quality of our clustering and summarization scheme in an experiment using several video clips.},
	keywords = {automatic video summarization, batch processing, batch processing (computers), Clustering algorithms, Clustering methods, clustering scheme, Computer science, Delaunay diagram, graph theory, Gunshot detection systems, Image sequences, mesh generation, Mobile computing, mobile radio, multidimensional point data cluster, Multidimensional systems, Multimedia communication, video clip, video frame content, Video sequences, video signal processing, wireless mobile environment},
	isbn = {0-7803-8533-0},
	doi = {10.1109/ICC.2004.1312767},
	author = {Yong Rao and Mundur, Padma and Yesha,Y.}
}
@article {12080,
	title = {Proactive key distribution using neighbor graphs},
	journal = {IEEE Wireless Communications},
	volume = {11},
	year = {2004},
	month = {2004/02//},
	pages = {26 - 36},
	abstract = {User mobility in wireless data networks is increasing because of technological advances, and the desire for voice and multimedia applications. These applications, however, require that handoffs between base stations (or access points) be fast to maintain the quality of the connections. In this article we introduce a novel data structure, the neighbor graph, that dynamically captures the mobility topology of a wireless network. We show how neighbor graphs can be utilized to obtain a 99 percent reduction in the authentication time of an IEEE 802.11 handoff (full EAP-TLS) by proactively distributing necessary key material one hop ahead of the mobile user. We also present a reactive method for fast authentication that requires only firmware changes to access points and hence can easily be deployed on existing wireless networks.},
	keywords = {access points, Authentication, authentication time, Base stations, Communication system security, Delay, graph theory, GSM, IEEE 802.11 handoff, Land mobile radio cellular systems, Message authentication, mobile radio, Multiaccess communication, neighbor graph, Network topology, Roaming, telecommunication security, Telephone sets, user mobility, Wi-Fi networks, wireless data networks, Wireless LAN, Wireless networks},
	isbn = {1536-1284},
	doi = {10.1109/MWC.2004.1269714},
	author = {Mishra,A. and Min Ho Shin and Petroni,N. L. and Clancy,T. C and Arbaugh, William A.}
}
@conference {16944,
	title = {A Rank-by-Feature Framework for Unsupervised Multidimensional Data Exploration Using Low Dimensional Projections},
	booktitle = {IEEE Symposium on Information Visualization, 2004. INFOVIS 2004},
	year = {2004},
	month = {2004///},
	pages = {65 - 72},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Exploratory analysis of multidimensional data sets is challenging because of the difficulty in comprehending more than three dimensions. Two fundamental statistical principles for the exploratory analysis are (1) to examine each dimension first and then find relationships among dimensions, and (2) to try graphical displays first and then find numerical summaries (D.S. Moore, (1999). We implement these principles in a novel conceptual framework called the rank-by-feature framework. In the framework, users can choose a ranking criterion interesting to them and sort 1D or 2D axis-parallel projections according to the criterion. We introduce the rank-by-feature prism that is a color-coded lower-triangular matrix that guides users to desired features. Statistical graphs (histogram, boxplot, and scatterplot) and information visualization techniques (overview, coordination, and dynamic query) are combined to help users effectively traverse 1D and 2D axis-parallel projections, and finally to help them interactively find interesting features},
	keywords = {axis-parallel projections, boxplot, color-coded lower-triangular matrix, computational complexity, computational geometry, Computer displays, Computer science, Computer vision, Data analysis, data mining, data visualisation, Data visualization, Displays, dynamic query, Educational institutions, exploratory data analysis, feature detection, feature detection/selection, Feature extraction, feature selection, graph theory, graphical displays, histogram, Information Visualization, interactive systems, Laboratories, Multidimensional systems, Principal component analysis, rank-by-feature prism, scatterplot, statistical analysis, statistical graphics, statistical graphs, unsupervised multidimensional data exploration, very large databases},
	isbn = {0-7803-8779-3},
	doi = {10.1109/INFVIS.2004.3},
	author = {Seo,J. and Shneiderman, Ben}
}
@conference {17583,
	title = {Dependent rounding in bipartite graphs},
	booktitle = {The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings},
	year = {2002},
	month = {2002///},
	pages = {323 - 332},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We combine the pipage rounding technique of Ageev \& Sviridenko with a recent rounding method developed by Srinivasan (2001), to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to the following applications: richer random-graph models for graphs with a given degree-sequence; improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties.},
	keywords = {Application software, Approximation algorithms, bipartite graph, bipartite graphs, broadcast channels, broadcast scheduling, Broadcasting, capacitated vertex cover, Character generation, computational complexity, Computer science, Delay, edge-sets, Educational institutions, fair scheduling, fractional vectors, graph theory, per-user fairness properties, pipage rounding technique, Processor scheduling, Random variables, random-graph models, randomized rounding approach, rounding method, scheduling, Scheduling algorithm, telecommunication computing, unrelated parallel machines},
	isbn = {0-7695-1822-2},
	doi = {10.1109/SFCS.2002.1181955},
	author = {Gandhi,R. and Khuller, Samir and Parthasarathy,S. and Srinivasan, Aravind}
}
@article {17667,
	title = {The one-inclusion graph algorithm is near-optimal for the prediction model of learning},
	journal = {IEEE Transactions on Information Theory},
	volume = {47},
	year = {2001},
	month = {2001/03//},
	pages = {1257 - 1261},
	abstract = {Haussler, Littlestone and Warmuth (1994) described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a mistake in terms of the number of examples seen and the Vapnik-Chervonenkis (VC) dimension of the concept class being learned. We show that their bound is within a factor of 1+o(1) of the best possible such bound for any algorithm},
	keywords = {Computer science, concept class, general-purpose algorithm, graph theory, learning prediction model, learning systems, near-optimal algorithm, Neural networks, one-inclusion graph algorithm, optimisation, Prediction algorithms, prediction theory, Predictive models, probability, Probability distribution, Upper bound, Vapnik-Chervonenkis dimension, Virtual colonoscopy},
	isbn = {0018-9448},
	doi = {10.1109/18.915700},
	author = {Li,Yi and Long,P. M and Srinivasan, Aravind}
}
@conference {17640,
	title = {Optimal design of signaling networks for Internet telephony},
	booktitle = {IEEE INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings},
	volume = {2},
	year = {2000},
	month = {2000///},
	pages = {707-716 vol.2 - 707-716 vol.2},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We present an approach for efficient design of a signaling network for a network of software switches supporting Internet telephony. While one may take an integer programming approach to solve this problem, it quickly becomes intractable even for modest-sized networks. Instead, our topology design uses random graphs that we show to be nearly optimal in cost, highly connected, and computationally efficient even for large networks. We then formulate a quadratic assignment problem (QAP) to map the abstract topology into the physical network to achieve optimal load balancing for given demand forecasts, which we solve using randomized heuristics. Numerical results on several example networks illustrate the performance and computational efficiency of our method. A graphical design tool has been developed based on our algorithms},
	keywords = {bandwidth allocation, Computational efficiency, Computer networks, Cost function, Demand forecasting, demand forecasts, graph theory, graphical design tool, Internet telephony, Linear programming, Load forecasting, Load management, Network topology, optimal design, optimal load balancing, optimisation, performance, quadratic assignment problem, random graphs, randomised algorithms, randomized heuristics, Signal design, signaling networks, Switches, telecommunication signalling, topology design},
	isbn = {0-7803-5880-5},
	doi = {10.1109/INFCOM.2000.832245},
	author = {Srinivasan, Aravind and Ramakrishnan,K. G and Kumaran,K. and Aravamudan,M. and Naqvi,S.}
}
@conference {17627,
	title = {Multicommodity flow and circuit switching},
	booktitle = {, Proceedings of the Thirty-First Hawaii International Conference on System Sciences, 1998},
	volume = {7},
	year = {1998},
	month = {1998/01/06/9},
	pages = {459-465 vol.7 - 459-465 vol.7},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Given a set of request pairs in a network, the problem of routing virtual circuits with low congestion is to connect each pair by a path so that few paths use the same link in the network. We build on an earlier multicommodity flow based approach of Leighton and Rao (1996) to show that short flow paths lead to path selections with low congestion. This shows that such good path selections exist for constant-degree expanders with strong expansion, generalizing a result of (Broder et al., 1994). We also show, for infinitely many n, n-vertex undirected graphs Gn along with a set T of connection requests, such that: T is fractionally realizable using flow-paths that impose a (fractional) congestion of at most 1; but any rounding of such a flow to the given set of flow-paths, leads to a congestion of Ω(log n/log log n). This is progress on a long-standing open problem},
	keywords = {Application software, Bandwidth, circuit switching, Computer science, constant-degree expanders, graph theory, High speed integrated circuits, Integrated circuit technology, Laboratories, low congestion, MATHEMATICS, multicommodity flow, National electric code, network routing, path selections, Routing, short flow paths, Switching circuits, switching theory, undirected graphs, virtual circuit routing},
	isbn = {0-8186-8255-8},
	doi = {10.1109/HICSS.1998.649241},
	author = {Leighton,T. and Rao,S. and Srinivasan, Aravind}
}
@conference {17607,
	title = {Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems},
	booktitle = {, 38th Annual Symposium on Foundations of Computer Science, 1997. Proceedings},
	year = {1997},
	month = {1997/10/20/22},
	pages = {416 - 425},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We present improved approximation algorithms for a family of problems involving edge-disjoint paths and unsplittable flow, and for some related routing problems. The central theme of all our algorithms is the underlying multi-commodity flow relaxation},
	keywords = {Approximation algorithms, Bandwidth, Channel allocation, computational complexity, Computer science, edge-disjoint paths, graph theory, High speed integrated circuits, IEL, Image motion analysis, Information systems, multi-commodity flow relaxation, Multiprocessor interconnection networks, network routing, Optical fiber networks, Routing, routing problems, unsplittable flow},
	isbn = {0-8186-8197-7},
	doi = {10.1109/SFCS.1997.646130},
	author = {Srinivasan, Aravind}
}
@conference {14576,
	title = {A distributed algorithm for ear decomposition},
	booktitle = {, Fifth International Conference on Computing and Information, 1993. Proceedings ICCI {\textquoteright}93},
	year = {1993},
	month = {1993/05/27/29},
	pages = {180 - 184},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {A distributed algorithm for finding an ear decomposition of an asynchronous communication network with n nodes and m links is presented. At the completion of the algorithm either the ears are correctly labeled or the nodes are informed that there exists no ear decomposition. First we present a novel algorithm to check the existence of an ear decomposition which uses O(m) messages. We also present two other algorithms, one which is time-optimal and the other which is message-optimal to determine the actual ears and their corresponding numbers after determining the existence of an ear decomposition},
	keywords = {Asynchronous communication, asynchronous communication network, Automata, Communication networks, computational complexity, Computer networks, Computer science, decomposition graph, distributed algorithm, distributed algorithms, Distributed computing, Ear, ear decomposition, graph theory, message-optimal, network decomposition, sorting, Testing, time-optimal},
	isbn = {0-8186-4212-2},
	doi = {10.1109/ICCI.1993.315382},
	author = {Hannenhalli, Sridhar and Perumalla,K. and Chandrasekharan,N. and Sridhar,R.}
}
@conference {14587,
	title = {Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs},
	booktitle = {, Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI {\textquoteright}92},
	year = {1992},
	month = {1992/05/28/30},
	pages = {42 - 45},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {The authors present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in O(n3) and O(n2) time respectively. Their algorithm for computing the matching polynomial generalizes an existing result from Lovasz, Plummer (1986) and the chromatic polynomial algorithm improves the result given by Hunt, Ravi, Stearn (1988) from O(n4) time},
	keywords = {chromatic polynomials, computational complexity, Computer science, graph colouring, graph theory, matching polynomial, Polynomials, series-parallel graphs, Terminology, Tree data structures, Tree graphs},
	isbn = {0-8186-2812-X},
	doi = {10.1109/ICCI.1992.227709},
	author = {Chandrasekharan,N. and Hannenhalli, Sridhar}
}
@article {17382,
	title = {Structural analysis of hypertexts: identifying hierarchies and useful metrics},
	journal = {ACM Transactions on Information Systems},
	volume = {10},
	year = {1992},
	month = {1992/04//},
	pages = {142 - 180},
	abstract = {Hypertext users often suffer from the {\textquotedblleft}lost in hyperspace{\textquotedblright} problem: disorientation from too many jumps while traversing a complex network. One solution to this problem is improved authoring to create more comprehensible structures. This paper proposes several authoring tools, based on hypertext structure analysis.In many hypertext systems authors are encouraged to create hierarchical structures, but when writing, the hierarchy is lost because of the inclusion of cross-reference links. The first part of this paper looks at ways of recovering lost hierarchies and finding new ones, offering authors different views of the same hypertext. The second part helps authors by identifying properties of the hypertext document. Multiple metrics are developed including compactness and stratum. Compactness indicates the intrinsic connectedness of the hypertext, and stratum reveals to what degree the hypertext is organized so that some nodes must be read before others.
Several existing hypertexts are used to illustrate the benefits of each technique. The collection of techniques provides a multifaceted view of the hypertext, which should allow authors to reduce undesired structural complexity and create documents that readers can traverse more easily.
},
	keywords = {graph theory, hierarchies, hypertext, metrics, structural analysis},
	isbn = {1046-8188},
	doi = {10.1145/146802.146826},
	url = {http://doi.acm.org/10.1145/146802.146826},
	author = {Botafogo,Rodrigo A. and Rivlin,Ehud and Shneiderman, Ben}
}
