OpenRaiser/Intern-Atlas huggingface dataset:
Graph Iterators: Decoupling Graph Structures from Algorithms
Venue: arXiv cs.DS 2010
Year: 2010

I will present a way to implement graph algorithms which is different from traditional methods. This work was motivated by the belief that some ideas from software engineering should be applied to graph algorithms. Re-usability of software is an important and difficult problem in general, and this is particularly true for graph algorithms. The scientific literature demonstrates plenty of applications of graph algorithms as subroutines for other algorithms. Moreover, many practical problems from various domains may be modeled as graph problems and hence solved by means of graph algorithms. Chapter 2 introduces some data structures that will be used in 5 basic graph algorithms in chapter 3. Chapter 4 discusses an implementation of a maximum cardinality matching algorithm for general graphs. Chapter 5 explains some techniques in C++, which are useful to implement the data structures and algorithms in an efficient way. Finally chapter 6 contains some concluding remarks.
Stability of Reeb graphs under function perturbations: the case of closed curves
Venue: arXiv cs.CG 2010
Year: 2010

Reeb graphs provide a method for studying the shape of a manifold by encoding the evolution and arrangement of level sets of a simple Morse function defined on the manifold. Since their introduction in computer graphics they have been gaining popularity as an effective tool for shape analysis and matching. In this context one question deserving attention is whether Reeb graphs are robust against function perturbations. Focusing on 1-dimensional manifolds, we define an editing distance between Reeb graphs of curves, in terms of the cost necessary to transform one graph into another. Our main result is that changes in Morse functions induce smaller changes in the editing distance between Reeb graphs of curves, implying stability of Reeb graphs under function perturbations.
Unique and Minimum Distance Decoding of Linear Codes with Reduced Complexity
Venue: arXiv cs.IT 2010
Year: 2010

We show that for (systematic) linear codes the time complexity of unique decoding is O(n^{2}q^{nRH(delta/2/R)}) and the time complexity of minimum distance decoding is O(n^{2}q^{nRH(delta/R)}). The proposed algorithm inspects all error patterns in the information set of the received message of weight less than d/2 or d, respectively.
Bounds for Bilinear Complexity of Noncommutative Group Algebras
Venue: arXiv cs.CC 2010
Year: 2010

We study the complexity of multiplication in noncommutative group algebras which is closely related to the complexity of matrix multiplication. We characterize such semisimple group algebras of the minimal bilinear complexity and show nontrivial lower bounds for the rest of the group algebras. These lower bounds are built on the top of Bläser's results for semisimple algebras and algebras with large radical and the lower bound for arbitrary associative algebras due to Alder and Strassen. We also show subquadratic upper bounds for all group algebras turning into "almost linear" provided the exponent of matrix multiplication equals 2.
Perceptual analyses of action-related impact sounds
Venue: arXiv cs.SD 2010
Year: 2010

Among environmental sounds, we have chosen to study a class of action-related impact sounds: automobile door closure sounds. We propose to describe these sounds using a model composed of perceptual properties. The development of the perceptual model was derived from the evaluation of many door closure sounds measured under controlled laboratory listening conditions. However, listening to such sounds normally occurs within a natural context, which probably modifies their perception. We therefore need to study differences between the real situation and the laboratory situation by following standard practices in order to specify the precise listening conditions and observe the influence of previous learning, expectations, action-perception interactions, and attention given to sounds. Our process consists in doing in situ experiments that are compared with specific laboratory experiments in order to isolate certain influential, context dependent components.
Local Popularity based Page Link Analysis
Venue: arXiv cs.IR 2010
Year: 2010

In this paper we introduce the concept of dynamic link pages. A web site/page contains a number of links to other pages. All the links are not equally important. Few links are more frequently visited and few rarely visited. In this scenario, identifying the frequently used links and placing them in the top left corner of the page will increase the user's satisfaction. This process will reduce the time spent by a visitor on the page, as most of the times, the popular links are presented in the visible part of the screen itself. Also, a site can be indexed based on the popular links in that page. This will increase the efficiency of the retrieval system. We presented a model to display the popular links, and also proposed a method to increase the quality of retrieval system.
SWiM -- A Semantic Wiki for Mathematical Knowledge Management
Venue: arXiv cs.DL 2010
Year: 2010

SWiM is a semantic wiki for collaboratively building, editing and browsing mathematical knowledge represented in the domain-specific structural semantic markup language OMDoc. It motivates users to contribute to collections of mathematical knowledge by instantly sharing the benefits of knowledge-powered services with them. SWiM is currently being used for authoring content dictionaries, i. e. collections of uniquely identified mathematical symbols, and prepared for managing a large-scale proof formalisation effort.
Enforcing the non-negativity constraint and maximum principles for diffusion with decay on general computational grids
Venue: arXiv cs.NA 2010
Year: 2010

In this paper, we consider anisotropic diffusion with decay, and the diffusivity coefficient to be a second-order symmetric and positive definite tensor. It is well-known that this particular equation is a second-order elliptic equation, and satisfies a maximum principle under certain regularity assumptions. However, the finite element implementation of the classical Galerkin formulation for both anisotropic and isotropic diffusion with decay does not respect the maximum principle. We first show that the numerical accuracy of the classical Galerkin formulation deteriorates dramatically with increase in the decay coefficient for isotropic medium and violates the discrete maximum principle. However, in the case of isotropic medium, the extent of violation decreases with mesh refinement. We then show that, in the case of anisotropic medium, the classical Galerkin formulation for anisotropic diffusion with decay violates the discrete maximum principle even at lower values of decay coefficient and does not vanish with mesh refinement. We then present a methodology for enforcing maximum principles under the classical Galerkin formulation for anisotropic diffusion with decay on general computational grids using optimization techniques. Representative numerical results (which take into account anisotropy and heterogeneity) are presented to illustrate the performance of the proposed formulation.
Computer Network Topology Design in Limelight of Pascal Graph Property
Venue: arXiv cs.NI 2010
Year: 2010

Constantly growing demands of high productivity and security of computer systems and computer networks call the interest of specialists in the environment of construction of optimum topologies of computer mediums. In earliest phases of design, the study of the topological influence of the processes that happen in computer systems and computer networks allows to obtain useful information which possesses a significant value in the subsequent design. It has always been tried to represent the different computer network topologies using appropriate graph models. Graphs have huge contributions towards the performance improvement factor of a network. Some major contributors are de-Bruijn, Hypercube, Mesh and Pascal. They had been studied a lot and different new features were always a part of research outcome. As per the definition of interconnection network it is equivalent that a suitable graph can represent the physical and logical layout very efficiently. In this present study Pascal graph is researched again and a new characteristics has been discovered. From the perspective of network topologies Pascal graph and its properties were first studied more than two decades back. Since then, a numerous graph models have emerged with potentials to be used as network topologies. This new property is guaranteed to make an everlasting mark towards the reliability of this graph to be used as a substantial contributor as a computer network topology. This shows its credentials over so many other topologies. This study reviews the characteristics of the Pascal graph and the new property is established using appropriate algorithm and the results.
Design of A Low Power Low Voltage CMOS Opamp
Venue: arXiv cs.OH 2010
Year: 2010

In this paper a CMOS operational amplifier is presented which operates at 2V power supply and 1microA input bias current at 0.8 micron technology using non conventional mode of operation of MOS transistors and whose input is depended on bias current. The unique behaviour of the MOS transistors in subthreshold region not only allows a designer to work at low input bias current but also at low voltage. While operating the device at weak inversion results low power dissipation but dynamic range is degraded. Optimum balance between power dissipation and dynamic range results when the MOS transistors are operated at moderate inversion. Power is again minimised by the application of input dependant bias current using feedback loops in the input transistors of the differential pair with two current substractors. In comparison with the reported low power low voltage opamps at 0.8 micron technology, this opamp has very low standby power consumption with a high driving capability and operates at low voltage. The opamp is fairly small (0.0084 mm 2) and slew rate is more than other low power low voltage opamps reported at 0.8 um technology [1,2]. Vittoz at al [3] reported that slew rate can be improved by adaptive biasing technique and power dissipation can be reduced by operating the device in weak inversion. Though lower power dissipation is achieved the area required by the circuit is very large and speed is too small. So, operating the device in moderate inversion is a good solution. Also operating the device in subthreshold region not only allows lower power dissipation but also a lower voltage operation is achieved.
Seidel complementation on ($P_5$, $House$, $Bull$)-free graphs
Venue: arXiv cs.DM 2010
Year: 2010

We consider the Seidel complementation on ($P_5, \bar{P_5}, Bull)$-free graphs
An LSB Data Hiding Technique Using Prime Numbers
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, a novel data hiding technique is proposed, as an improvement over the Fibonacci LSB data-hiding technique proposed by Battisti et al. First we mathematically model and generalize our approach. Then we propose our novel technique, based on decomposition of a number (pixel-value) in sum of prime numbers. The particular representation generates a different set of (virtual) bit-planes altogether, suitable for embedding purposes. They not only allow one to embed secret message in higher bit-planes but also do it without much distortion, with a much better stego-image quality, and in a reliable and secured manner, guaranteeing efficient retrieval of secret message. A comparative performance study between the classical Least Significant Bit (LSB)method, the Fibonacci LSB data-hiding technique and our proposed schemes has been done. Analysis indicates that image quality of the stego-image hidden by the technique using Fibonacci decomposition improves against that using simple LSB substitution method, while the same using the prime decomposition method improves drastically against that using Fibonacci decomposition technique. Experimental results show that, the stego-image is visually indistinguishable from the original cover-image.
Stability of epsilon-Kernels
Venue: arXiv cs.CG 2010
Year: 2010

Given a set P of n points in |R^d, an eps-kernel K subset P approximates the directional width of P in every direction within a relative (1-eps) factor. In this paper we study the stability of eps-kernels under dynamic insertion and deletion of points to P and by changing the approximation factor eps. In the first case, we say an algorithm for dynamically maintaining a eps-kernel is stable if at most O(1) points change in K as one point is inserted or deleted from P. We describe an algorithm to maintain an eps-kernel of size O(1/eps^{(d-1)/2}) in O(1/eps^{(d-1)/2} + log n) time per update. Not only does our algorithm maintain a stable eps-kernel, its update time is faster than any known algorithm that maintains an eps-kernel of size O(1/eps^{(d-1)/2}). Next, we show that if there is an eps-kernel of P of size k, which may be dramatically less than O(1/eps^{(d-1)/2}), then there is an (eps/2)-kernel of P of size O(min {1/eps^{(d-1)/2}, k^{floor(d/2)} log^{d-2} (1/eps)}). Moreover, there exists a point set P in |R^d and a parameter eps > 0 such that if every eps-kernel of P has size at least k, then any (eps/2)-kernel of P has size Omega(k^{floor(d/2)}).
A Study of Bandwidth-Perception Management Mechanisms in IEEE 802.16 Networks
Venue: arXiv cs.NI 2010
Year: 2010

Bandwidth request-grant mechanisms are used in 802.16 networks to manage the uplink bandwidth needs of subscriber stations (SSs). Requests may be sent by SSs to the base station (BS) by means of several mechanisms defined in the standard. Based on the incoming requests, the BS (which handles most of the bandwidth scheduling in the system) schedules the transmission of uplink traffic, by assigning transmission opportunities to the SSs in an implementation-dependent manner. In this paper we present a study of some bandwidth allocation issues, arising from the management of the perception of subscriber stations' bandwidth needs at the base station. We illustrate how the bandwidth perception varies depending on the policy used to handle requests and grants. By means of ns-2 simulations, we evaluate the potential impact of such policies on the system's aggregate throughput when the traffic is composed of Best-Effort TCP flows.
Psychophysiological Correlations with Gameplay Experience Dimensions
Venue: arXiv cs.HC 2010
Year: 2010

In this paper, we report a case study using two easy-to-deploy psychophysiological measures - electrodermal activity (EDA) and heart rate (HR) - and correlating them with a gameplay experience questionnaire (GEQ) in an attempt to establish this mixed-methods approach for rapid application in a commercial game development context. Results indicate that there is a statistically significant correlation (p < 0.01) between measures of psychophysiological arousal (HR, EDA) and self-reported UX in games (GEQ), with some variation between the EDA and HR measures. Results are consistent across three major commercial First-Person Shooter (FPS) games.
Shadowing Effects on Routing Protocol of Multihop Ad Hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

Two-ray ground reflection model has been widely used as the propagation model to investigate the performance of an ad hoc network. But two-ray model is too simple to represent a real world network. A more realistic model namely shadowing propagation model has been used in this investigation. Under shadowing propagation model, a mobile node may receive a packet at a signal level that is below a required threshold level. This low signal level affects the routing protocol as well as the medium access control protocol of a network. An analytical model has been presented in this paper to investigate the shadowing effects on the network performance. The analytical model has been verified via simulation results. Simulation results show that the performance of a network becomes very poor if shadowing propagation model is used in compare to the simple two-ray model. Two solutions have also been proposed in this paper to overcome the effects of shadowing. One solution is a physical layer solution and the other one is a Medium Access Control (MAC) layer solution. Simulation results show that these two solutions reduce the shadowing effect and improve network performance.
Querying for the Largest Empty Geometric Object in a Desired Location
Venue: arXiv cs.CG 2010
Year: 2010

We study new types of geometric query problems defined as follows: given a geometric set $P$, preprocess it such that given a query point $q$, the location of the largest circle that does not contain any member of $P$, but contains $q$ can be reported efficiently. The geometric sets we consider for $P$ are boundaries of convex and simple polygons, and point sets. While we primarily focus on circles as the desired shape, we also briefly discuss empty rectangles in the context of point sets.
Effect of Inter Packet Delay in performance analysis of coexistence heterogeneous Wireless Packet Networks
Venue: arXiv cs.NI 2010
Year: 2010

As the explosive growth of the ISM band usage continues, there are many scenarios where different systems operate in the same place at the same time. One of growing concerns is the coexistence of heterogeneous wireless network systems. For the successful deployment of mission-critical systems such as wireless sensor networks, it is required to provide a solution for the coexistence. In this paper, we propose a new scheme using inter packet delay for the coexistence of IEEE 802.15.4 LRWPAN and IEEE 802.11b WLAN. To evaluate the effectiveness of the proposed scheme, measurement and simulation study are conducted using Qualnet 4.5 simulation software. The simulation results show that the proposed scheme is effective in performance improvement for coexistence network of IEEE 802.15.4 for various topologies.
The Isomorphism Problem for omega-Automatic Trees
Venue: arXiv cs.LO 2010
Year: 2010

The main result of this paper is that the isomorphism for omega-automatic trees of finite height is at least has hard as second-order arithmetic and therefore not analytical. This strengthens a recent result by Hjorth, Khoussainov, Montalban, and Nies showing that the isomorphism problem for omega-automatic structures is not $Σ^1_2$. Moreover, assuming the continuum hypothesis CH, we can show that the isomorphism problem for omega-automatic trees of finite height is recursively equivalent with second-order arithmetic. On the way to our main results, we show lower and upper bounds for the isomorphism problem for omega-automatic trees of every finite height: (i) It is decidable ($Π^0_1$-complete, resp,) for height 1 (2, resp.), (ii) $Π^1_1$-hard and in $Π^1_2$ for height 3, and (iii) $Π^1_{n-3}$- and $Σ^1_{n-3}$-hard and in $Π^1_{2n-4}$ (assuming CH) for all n > 3. All proofs are elementary and do not rely on theorems from set theory.
Effects of component-subscription network topology on large-scale data centre performance scaling
Venue: arXiv cs.DC 2010
Year: 2010

Modern large-scale date centres, such as those used for cloud computing service provision, are becoming ever-larger as the operators of those data centres seek to maximise the benefits from economies of scale. With these increases in size comes a growth in system complexity, which is usually problematic. There is an increased desire for automated "self-star" configuration, management, and failure-recovery of the data-centre infrastructure, but many traditional techniques scale much worse than linearly as the number of nodes to be managed increases. As the number of nodes in a median-sized data-centre looks set to increase by two or three orders of magnitude in coming decades, it seems reasonable to attempt to explore and understand the scaling properties of the data-centre middleware before such data-centres are constructed. In [1] we presented SPECI, a simulator that predicts aspects of large-scale data-centre middleware performance, concentrating on the influence of status changes such as policy updates or routine node failures. [...]. In [1] we used a first-approximation assumption that such subscriptions are distributed wholly at random across the data centre. In this present paper, we explore the effects of introducing more realistic constraints to the structure of the internal network of subscriptions. We contrast the original results [...] exploring the effects of making the data-centre's subscription network have a regular lattice-like structure, and also semi-random network structures resulting from parameterised network generation functions that create "small-world" and "scale-free" networks. We show that for distributed middleware topologies, the structure and distribution of tasks carried out in the data centre can significantly influence the performance overhead imposed by the middleware.
Rate Regions of Secret Key Sharing in a New Source Model
Venue: arXiv cs.IT 2010
Year: 2010

A source model for secret key generation between terminals is considered. Two users, namely users 1 and 2, at one side communicate with another user, namely user 3, at the other side via a public channel where three users can observe i.i.d. outputs of correlated sources. Each of users 1 and 2 intends to share a secret key with user 3 where user 1 acts as a wiretapper for user 2 and vice versa. In this model, two situations are considered: communication from users 1 and 2 to user 3 (the forward key strategy) and from user 3 to users 1 and 2 (the backward key strategy). In both situations, the goal is sharing a secret key between user 1 and user 3 while leaking no effective information about that key to user 2, and simultaneously, sharing another secret key between user 2 and user 3 while leaking no effective information about the latter key to user 1. This model is motivated by wireless communications when considering user 3 as a base station and users 1 and 2 as network users. In this paper, for both the forward and backward key strategies, inner and outer bounds of secret key capacity regions are derived. In special situations where one of users 1 and 2 is only interested in wiretapping and not key sharing, our results agree with that of Ahlswede and Csiszar. Also, we investigate some special cases in which the inner bound coincides with the outer bound and secret key capacity region is deduced.
On the Complexity of Local Search for Weighted Standard Set Problems
Venue: arXiv cs.CC 2010
Year: 2010

In this paper, we study the complexity of computing locally optimal solutions for weighted versions of standard set problems such as SetCover, SetPacking, and many more. For our investigation, we use the framework of PLS, as defined in Johnson et al., [JPY88]. We show that for most of these problems, computing a locally optimal solution is already PLS-complete for a simple neighborhood of size one. For the local search versions of weighted SetPacking and SetCover, we derive tight bounds for a simple neighborhood of size two. To the best of our knowledge, these are one of the very few PLS results about local search for weighted standard set problems.
Relaxation-based coarsening and multiscale graph organization
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we generalize and improve the multiscale organization of graphs by introducing a new measure that quantifies the "closeness" between two nodes. The calculation of the measure is linear in the number of edges in the graph and involves just a small number of relaxation sweeps. A similar notion of distance is then calculated and used at each coarser level. We demonstrate the use of this measure in multiscale methods for several important combinatorial optimization problems and discuss the multiscale graph organization.