OpenRaiser/Intern-Atlas huggingface dataset:
Domination in graphs with bounded propagation: algorithms, formulations and hardness results
Venue: arXiv cs.DS 2008
Year: 2008

We introduce a hierarchy of problems between the \textsc{Dominating Set} problem and the \textsc{Power Dominating Set} (PDS) problem called the $\ell$-round power dominating set ($\ell$-round PDS, for short) problem. For $\ell=1$, this is the \textsc{Dominating Set} problem, and for $\ell\geq n-1$, this is the PDS problem; here $n$ denotes the number of nodes in the input graph. In PDS the goal is to find a minimum size set of nodes $S$ that power dominates all the nodes, where a node $v$ is power dominated if (1) $v$ is in $S$ or it has a neighbor in $S$, or (2) $v$ has a neighbor $u$ such that $u$ and all of its neighbors except $v$ are power dominated. Note that rule (1) is the same as for the \textsc{Dominating Set} problem, and that rule (2) is a type of propagation rule that applies iteratively. The $\ell$-round PDS problem has the same set of rules as PDS, except we apply rule (2) in ``parallel'' in at most $\ell-1$ rounds. We prove that $\ell$-round PDS cannot be approximated better than $2^{\log^{1-ε}{n}}$ even for $\ell=4$ in general graphs. We provide a dynamic programming algorithm to solve $\ell$-round PDS optimally in polynomial time on graphs of bounded tree-width. We present a PTAS (polynomial time approximation scheme) for $\ell$-round PDS on planar graphs for $\ell=O(\tfrac{\log{n}}{\log{\log{n}}})$. Finally, we give integer programming formulations for $\ell$-round PDS.
Choice numbers of graphs
Venue: arXiv cs.DM 2008
Year: 2008

A solution to a problem of Erdős, Rubin and Taylor is obtained by showing that if a graph $G$ is $(a:b)$-choosable, and $c/d > a/b$, then $G$ is not necessarily $(c:d)$-choosable. The simplest case of another problem, stated by the same authors, is settled, proving that every 2-choosable graph is also $(4:2)$-choosable. Applying probabilistic methods, an upper bound for the $k^{th}$ choice number of a graph is given. We also prove that a directed graph with maximum outdegree $d$ and no odd directed cycle is $(k(d+1):k)$-choosable for every $k \geq 1$. Other results presented in this article are related to the strong choice number of graphs (a generalization of the strong chromatic number). We conclude with complexity analysis of some decision problems related to graph choosability.
Digraph Decompositions and Monotonicity in Digraph Searching
Venue: arXiv cs.DM 2008
Year: 2008

We consider monotonicity problems for graph searching games. Variants of these games - defined by the type of moves allowed for the players - have been found to be closely connected to graph decompositions and associated width measures such as path- or tree-width. Of particular interest is the question whether these games are monotone, i.e. whether the cops can catch a robber without ever allowing the robber to reach positions that have been cleared before. The monotonicity problem for graph searching games has intensely been studied in the literature, but for two types of games the problem was left unresolved. These are the games on digraphs where the robber is invisible and lazy or visible and fast. In this paper, we solve the problems by giving examples showing that both types of games are non-monotone. Graph searching games on digraphs are closely related to recent proposals for digraph decompositions generalising tree-width to directed graphs. These proposals have partly been motivated by attempts to develop a structure theory for digraphs similar to the graph minor theory developed by Robertson and Seymour for undirected graphs, and partly by the immense number of algorithmic results using tree-width of undirected graphs and the hope that part of this success might be reproducible on digraphs using a directed tree-width. Unfortunately the number of applications for the digraphs measures introduced so far is still small. We therefore explore the limits of the algorithmic applicability of digraph decompositions. In particular, we show that various natural candidates for problems that might benefit from digraphs having small directed tree-width remain NP-complete even on almost acyclic graphs.
Textual Fingerprinting with Texts from Parkin, Bassewitz, and Leander
Venue: arXiv cs.CL 2008
Year: 2008

Current research in author profiling to discover a legal author's fingerprint does not only follow examinations based on statistical parameters only but include more and more dynamic methods that can learn and that react adaptable to the specific behavior of an author. But the question on how to appropriately represent a text is still one of the fundamental tasks, and the problem of which attribute should be used to fingerprint the author's style is still not exactly defined. In this work, we focus on linguistic selection of attributes to fingerprint the style of the authors Parkin, Bassewitz and Leander. We use texts of the genre Fairy Tale as it has a clear style and texts of a shorter size with a straightforward story-line and a simple language.
On Maximizing Coverage in Gaussian Relay Networks
Venue: arXiv cs.IT 2008
Year: 2008

Results for Gaussian relay channels typically focus on maximizing transmission rates for given locations of the source, relay and destination. We introduce an alternative perspective, where the objective is maximizing coverage for a given rate. The new objective captures the problem of how to deploy relays to provide a given level of service to a particular geographic area, where the relay locations become a design parameter that can be optimized. We evaluate the decode and forward (DF) and compress and forward (CF) strategies for the relay channel with respect to the new objective of maximizing coverage. When the objective is maximizing rate, different locations of the destination favor different strategies. When the objective is coverage for a given rate, and the relay is able to decode, DF is uniformly superior in that it provides coverage at any point served by CF. When the channel model is modified to include random fading, we show that the monotone ordering of coverage regions is not always maintained. While the coverage provided by DF is sensitive to changes in the location of the relay and the path loss exponent, CF exhibits a more graceful degradation with respect to such changes. The techniques used to approximate coverage regions are new and may be of independent interest.
Sign Language Tutoring Tool
Venue: arXiv cs.LG 2008
Year: 2008

In this project, we have developed a sign language tutor that lets users learn isolated signs by watching recorded videos and by trying the same signs. The system records the user's video and analyses it. If the sign is recognized, both verbal and animated feedback is given to the user. The system is able to recognize complex signs that involve both hand gestures and head movements and expressions. Our performance tests yield a 99% recognition rate on signs involving only manual gestures and 85% recognition rate on signs that involve both manual and non manual components, such as head movement and facial expressions.
Min-Cost 2-Connected Subgraphs With k Terminals
Venue: arXiv cs.DS 2008
Year: 2008

In the k-2VC problem, we are given an undirected graph G with edge costs and an integer k; the goal is to find a minimum-cost 2-vertex-connected subgraph of G containing at least k vertices. A slightly more general version is obtained if the input also specifies a subset S \subseteq V of terminals and the goal is to find a subgraph containing at least k terminals. Closely related to the k-2VC problem, and in fact a special case of it, is the k-2EC problem, in which the goal is to find a minimum-cost 2-edge-connected subgraph containing k vertices. The k-2EC problem was introduced by Lau et al., who also gave a poly-logarithmic approximation for it. No previous approximation algorithm was known for the more general k-2VC problem. We describe an O(\log n \log k) approximation for the k-2VC problem.
On Subgraph Isomorphism
Venue: arXiv cs.DM 2008
Year: 2008

Article explicitly expresses Subgraph Isomorphism by a polynomial size asymmetric linear system.
Convergence Thresholds of Newton's Method for Monotone Polynomial Equations
Venue: arXiv cs.DS 2008
Year: 2008

Monotone systems of polynomial equations (MSPEs) are systems of fixed-point equations $X_1 = f_1(X_1, ..., X_n),$ $..., X_n = f_n(X_1, ..., X_n)$ where each $f_i$ is a polynomial with positive real coefficients. The question of computing the least non-negative solution of a given MSPE $\vec X = \vec f(\vec X)$ arises naturally in the analysis of stochastic models such as stochastic context-free grammars, probabilistic pushdown automata, and back-button processes. Etessami and Yannakakis have recently adapted Newton's iterative method to MSPEs. In a previous paper we have proved the existence of a threshold $k_{\vec f}$ for strongly connected MSPEs, such that after $k_{\vec f}$ iterations of Newton's method each new iteration computes at least 1 new bit of the solution. However, the proof was purely existential. In this paper we give an upper bound for $k_{\vec f}$ as a function of the minimal component of the least fixed-point $μ\vec f$ of $\vec f(\vec X)$. Using this result we show that $k_{\vec f}$ is at most single exponential resp. linear for strongly connected MSPEs derived from probabilistic pushdown automata resp. from back-button processes. Further, we prove the existence of a threshold for arbitrary MSPEs after which each new iteration computes at least $1/w2^h$ new bits of the solution, where $w$ and $h$ are the width and height of the DAG of strongly connected components.
A Theory for Valiant's Matchcircuits (Extended Abstract)
Venue: arXiv cs.CC 2008
Year: 2008

The computational function of a matchgate is represented by its character matrix. In this article, we show that all nonsingular character matrices are closed under matrix inverse operation, so that for every $k$, the nonsingular character matrices of $k$-bit matchgates form a group, extending the recent work of Cai and Choudhary (2006) of the same result for the case of $k=2$, and that the single and the two-bit matchgates are universal for matchcircuits, answering a question of Valiant (2002).
Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees
Venue: arXiv cs.DS 2008
Year: 2008

Consider a set of labels $L$ and a set of trees ${\mathcal T} = \{{\mathcal T}^{(1), {\mathcal T}^{(2), ..., {\mathcal T}^{(k) \$ where each tree ${\mathcal T}^{(i)$ is distinctly leaf-labeled by some subset of $L$. One fundamental problem is to find the biggest tree (denoted as supertree) to represent $\mathcal T}$ which minimizes the disagreements with the trees in ${\mathcal T}$ under certain criteria. This problem finds applications in phylogenetics, database, and data mining. In this paper, we focus on two particular supertree problems, namely, the maximum agreement supertree problem (MASP) and the maximum compatible supertree problem (MCSP). These two problems are known to be NP-hard for $k \geq 3$. This paper gives the first polynomial time algorithms for both MASP and MCSP when both $k$ and the maximum degree $D$ of the trees are constant.
A New Approach to Spreadsheet Analytics Management in Financial Markets
Venue: arXiv cs.SE 2008
Year: 2008

Spreadsheets in financial markets are frequently used as database, calculator and reporting application combined. This paper describes an alternative approach in which spreadsheet design and database technology have been brought together in order to alleviate management and regulatory concerns over the operational risks of spreadsheet usage. In particular, the paper focuses on the rapid creation and centralised deployment of statistical analytics within a software system now in use by major investment banks, and presents a novel technique for the manipulation in spreadsheets of high volumes of intraday market data.
A Novel X-Axis Tuning Fork Gyroscope with "8 Vertical Springs-Proofmass" Structure on (111)-Silicon
Venue: arXiv cs.OH 2008
Year: 2008

A novel x-axis tuning fork MEMS gyroscope with "8 vertical springs-proofmass" structure for Coriolis effect detection is presented. Compared with the common single-plane springs, the 8 vertical springs, symmetrically located at the top and bottom sides, more stably suspend the large thick proofmass featuring large capacitance variation and low mechanical noise. A bulk-micromachining technology is applied to obtain the large proofmass and twins-like dual beams. During the fabrication process, the dimensions of the 8 vertical springs are precisely confined by thermal oxide protected limit trenches (LTs) sidewalls and the extreme slowly etched (111)-planes; therefore a small mismatch of less than 30 Hz is achieved before tuning. Initial test shows a sensitivity of 0.15mV/(deg/s) and rate resolution around 0.1deg/s under atmosphere pressure.
High Efficiency 3-Phase Cmos Rectifier with Step Up and Regulated
Venue: arXiv cs.OH 2008
Year: 2008

This paper presents several design issues related to the monolithic integration of a 3-phase AC to DC low voltage, low power rectifier for 3-phase micro source electrical conditioning. Reduced input voltage operation (down to 1V), high efficiency, and output voltage regulations are implemented, based on commercially available CMOS technology. Global design and system issues are detailed. The management of start-up sequences under self supplied conditions as well as output voltage regulations are specifically addressed. Simulation results, practical implementation and validation are presented. They are based on the association of three micro elements : a 3-phase micro-generator, a stand alone 3-phase AC to DC integrated rectifier, and an output voltage conditioner based on a commercially available IC.
Silicon microneedles array with biodegradable tips for transdermal drug delivery
Venue: arXiv cs.OH 2008
Year: 2008

This paper presents the fabrication process, characterization results and basic functionality of silicon microneedles array with biodegradable tips. In order to avoid the main problems related to silicon microneedles : broking of the top part of the needles inside the skin, a simple solution can be fabrication of microneedles array with biodegradable tips. The silicon microneedles array was fabricated by using reactive ion etching while the biodegradable tips were performed using and anodization process that generates selectively porous silicon only on the top part of the skin. The paper presents also the results of in vitro release of calcein using microneedles array with biodegradable tips
2-D Analysis of Enhancement of Analytes Adsorption Due to Flow Stirring by Electrothermal Force in The Microcantilever Sensor
Venue: arXiv cs.OH 2008
Year: 2008

Ac electrokinetic flows are commonly used for manipulating micron-scale particles in a biosensor system. At the solid-liquid state there are two kinds of processes in the reaction between analytes and ligands: the mass transport process and the chemical reaction process. The mass transport process is related to convection and diffusion. Total or partial limit of mass transport would retard the diffusion from the bulk fluid to the interface of reaction. This effect decreases the possibility of adsorption of analyte and ligand because the chemical reaction is faster than the diffusion. In order to solve this problem, we apply an ac electric field to induce a vortex field by the electrothermal effect, which helps in increasing the rate of diffusion. By using the finite element analysis software, COMSOL Multiphysics, we optimized several parameters of the microelectrode structures and the position of the reacting surface, i.e. the microcantilever, by a simplified 2-D model and a 3-D model. It is successful in accelerating the reacting rate of the molecule which is limited by mass transport. The factor of the efficiency is about 1.429 when the operating voltage is 15 Vrms peak-to-peak. In addition, the surface concentration of the complex on the microcantilever has been simulated.
Solving functional reliability issue for an optical electrostatic switch
Venue: arXiv cs.OH 2008
Year: 2008

In this paper, we report the advantage of using AC actuating signal for driving MEMS actuators instead of DC voltages. The study is based upon micro mirror devices used in digital mode for optical switching operation. When the pull-in effect is used, charge injection occurs when the micro mirror is maintained in the deflected position. To avoid this effect, a geometrical solution is to realize grounded landing electrodes which are electro-statically separated from the control electrodes. Another solution is the use of AC signal which eliminates charge injection particularly if a bipolar signal is used. Long term experiments have demonstrated the reliability of such a signal command to avoid injection of electric charges.
Out-of-Plane Cmos Compatible Magnetometers
Venue: arXiv cs.OH 2008
Year: 2008

Three-dimensional MEMS magnetometers with use of residual stresses in thin multilayers cantilevers are presented. Half-loop cantilevers based on Lorentz-force deflection convert magnetic flux in changes, thanks to piezoresistive transducers mounted in Wheatstone bridge. Magnetic field in the order of 10 Gauss was measured with a sensitivity of 0.015 mV/Gauss. A Finite Element Model of the device has been developed with Ansys for static and dynamic simulations. Novel out-of-plane ferromagnetic nickel plate magnetometer is also presented.
Lamination And Microstructuring Technology for a Bio-Cell Multiwell array
Venue: arXiv cs.OH 2008
Year: 2008

Microtechnology becomes a versatile tool for biological and biomedical applications. Microwells have been established long but remained non-intelligent up to now. Merging new fabrication techniques and handling concepts with microelectronics enables to realize intelligent microwells suitable for future improved cancer treatment. The described technology depicts the basis for the fabrication of a elecronically enhanced microwell. Thin aluminium sheets are structured by laser micro machining and laminated successively to obtain registration tolerances of the respective layers of 5..10Â$μ$m. The microwells lasermachined into the laminate are with 50..80Â$μ$m diameter, allowing to hold individual cells within the well. The individual process steps are described and results on the microstructuring are given.
Profile Control of a Borosilicate-Glass Groove Formed by Deep Reactive Ion Etching
Venue: arXiv cs.OH 2008
Year: 2008

Deep reactive ion etching (DRIE) of borosilicate glass and profile control of an etched groove are reported. DRIE was carried out using an anodically bonded silicon wafer as an etching mask. We controlled the groove profile, namely improving its sidewall angle, by removing excessively thick polymer film produced by carbonfluoride etching gases during DRIE. Two fabrication processes were experimentally compared for effective removal of the film : DRIE with the addition of argon to the etching gases and a novel combined process in which DRIE and subsequent ultrasonic cleaning in DI water were alternately carried out. Both processes improved the sidewall angle, and it reached 85o independent of the mask-opening width. The results showed the processes can remove excessive polymer film on sidewalls. Accordingly, the processes are an effective way to control the groove profile of borosilicate glass.
From MEMS Devices to Smart Integrated Systems
Venue: arXiv cs.OH 2008
Year: 2008

The smart integrated systems of tomorrow would demand a combination of micromechanical components and traditional electronics. On-chip solutions will be the ultimate goal. One way of making such systems is to implement the mechanical parts in an ordinary CMOS process. This procedure has been used to design an oscillator consisting of a resonating cantilever beam and a CMOS Pierce feedback amplifier. The resonating frequency is changed if the beam is bent by external forces. The paper describes central features of this procedure and highlights the design considerations for the CMOS-MEMS oscillator. The circuit is used as an example of a "VLSI designer" way of making future integrated micromechanical and microelectronic systems on-chip. The possibility for expansion to larger systems is reviewed.
The Forgiving Tree: A Self-Healing Distributed Data Structure
Venue: arXiv cs.DC 2008
Year: 2008

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that the following process continues for up to n rounds where n is the total number of nodes initially in the network: the adversary deletes an arbitrary node from the network, then the network responds by quickly adding a small number of new edges. We present a distributed data structure that ensures two key properties. First, the diameter of the network is never more than $O(\log Δ)$ times its original diameter, where $Δ$ is the maximum degree of the network initially. We note that for many peer-to-peer systems, $Δ$ is polylogarithmic, so the diameter increase would be a O(log log n) multiplicative factor. Second, the degree of any node never increases by more than 3 over its original degree. Our data structure is fully distributed, has O(1) latency per round and requires each node to send and receive O(1) messages per round. The data structure requires an initial setup phase that has latency equal to the diameter of the original network, and requires, with high probability, each node v to send O(log n) messages along every edge incident to v. Our approach is orthogonal and complementary to traditional topology-based approaches to defending against attack.
Implementing a Test Strategy for an Advanced Video Acquisition and Processing Architecture
Venue: arXiv cs.CV 2008
Year: 2008

This paper presents some aspects related to test process of an advanced video system used in remote IP surveillance. The system is based on a Pentium compatible architecture using the industrial standard PC104+. First the overall architecture of the system is presented, involving both hardware or software aspects. The acquisition board which is developed in a special, nonstandard architecture, is also briefly presented. The main purpose of this research was to set a coherent set of procedures in order to test all the aspects of the video acquisition board. To accomplish this, it was necessary to set-up a procedure in two steps: stand alone video board test (functional test) and an in-system test procedure verifying the compatibility with both OS: Linux and Windows. The paper presents also the results obtained using this procedure.
An Algebraic Characterization of Security of Cryptographic Protocols
Venue: arXiv cs.CR 2008
Year: 2008

Several of the basic cryptographic constructs have associated algebraic structures. Formal models proposed by Dolev and Yao to study the (unconditional) security of public key protocols form a group. The security of some types of protocols can be neatly formulated in this algebraic setting. We investigate classes of two-party protocols. We then consider extension of the formal algebraic framework to private-key protocols. We also discuss concrete realization of the formal models. In this case, we propose a definition in terms of pseudo-free groups.