An O(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V,E). The expected running time of our algorithm is Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n-1; so the expected running time of our algorithm for simple unweighted graphs is Õ(mn).All the algorithms currently known for constructing a Gomory-Hu tree [8,9] use n-1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest Õ(n20/9) max flow algorithm due to Karger and Levine [11] yields the current best running time of Õ(n20/9n) for Gomory-Hu tree construction on simpleunweighted graphs with m edges and n vertices. Thus we present the first Õ(mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs.We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S ⊆ V can be reused for computing a minimum Steiner cut for certain Steiner sets S' ⊆ S.

Faster algorithms for all-pairs small stretch distances in weighted graphs

Abstract. Let G = (V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in G. While many efficient algorithms are known for this problem in unweighted graphs, not many results are known for this problem in weighted graphs. Zwick [14] showed that for any fixed ε> 0, stretch 1 1 + ε distances between all pairs of vertices in a weighted directed graph on n vertices can be computed in Õ(n ω) time, where ω < 2.376 is the exponent of matrix multiplication and n is the number of vertices. It is known that finding distances of stretch less than 2 between all pairs of vertices in G is at least as hard as Boolean matrix multiplication of two n×n matrices. It is also known that all-pairs stretch 3 distances can be computed in Õ(n 2) time and all-pairs stretch 7/3 distances can be computed in Õ(n 7/3) time. Here we consider efficient algorithms for the problem of computing all-pairs stretch (2+ε) distances in G, for any 0 < ε < 1. We show that all pairs stretch (2 + ε) distances for any fixed ε> 0 in G can be computed in expected time O(n 9/4 logn). This algorithm uses a fast rectangular matrix multiplication subroutine. We also present a combinatorial algorithm (that is, it does not use fast matrix multiplication) with expected running time O(n 9/4) for computing all-pairs stretch 5/2 distances in G. 1

Tracking performance of an LMS-Linear Equalizer for fading channels

We consider a time varying wireless fading channel, equalized by an LMS linear equalizer. We study how well this equalizer tracks the optimal Wiener equalizer. We model the channel by an Auto-regressive (AR) process. Then the LMS equalizer and the AR process are jointly approximated by the solution of a system of ODEs (ordinary differential equations). Using these ODEs, the error between the LMS equalizer and the instantaneous Wiener filter is shown to decay exponentially/polynomially to zero unless the channel is marginally stable in which case the convergence may not hold.Using the same ODEs, we also show that the corresponding Mean Square Error (MSE) converges towards minimum MSE(MMSE) at the same rate for a stable channel. We further show that the difference between the MSE and the MMSE does not explode with time even when the channel is unstable. Finally we obtain an optimum step size for the linear equalizer in terms of the AR parameters, whenever the error decay is exponential.

LMS versus Wiener filter for a decision feedback equalizer

In this paper we study an LMS-DFE. We use the ODE framework to show that the LMS-DFE attractors are close to the true DFE Wiener filter (designed considering the decision errors) at high SNR. Therefore, via LMS one can obtain a computationally efficient way to obtain the true DFE Wiener filter under high SNR. We also provide examples to show that the DFE filter so obtained can significantly outperform the usual DFE Wiener filter (designed assuming perfect decisions) at all practical SNRs. In fact, the performance improvement is very significant even at high SNRs (up to 50%), where the popular Wiener filter designed with perfect decisions, is believed to be closer to the optimal one.

Synthesis and Antileukemic Activity of Novel 2-(4-(2,4-dimethoxybenzoyl)phenoxy)-1-(4-(3-(piperidin-4-yl)propyl)piper idin-1-yl)ethanone Derivatives

A series of novel 2-(4-(2,4-dimethoxybenzoyl)phenoxy)-1-(4-(3-(piperidin-4-yl)propyl) piperidin-1-yl)ethanone derivatives 9(ae) and 10(ag) were synthesized and characterized by 1H NMR, IR, mass spectral, and elemental analysis. These novel compounds were evaluated for their antileukemic activity against two human leukemic cell lines (K562 and CEM) by using the 3-(4,5-dimethylthiazol-2-yl)-2,5-diphenyltetrazoliumbromide assay. Some of the tested compounds showed good antiproliferative activity with IC50 values ranging from 1.6 to 8.0 mu m. Compound 9c, 9e, and 10f with an electron-withdrawing halogen substituent at the para position on the phenyl ring showed excellent in vitro potency against tested human leukemia cells (K562 and CEM).

An (O)over-bar(m(2)n) randomized algorithm to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis in a directed graph G. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {- 1, 0, 1} incidence vector is associated with each cycle and the vector space over Q generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m arcs and n vertices runs in O(m(w+1)n) time (where w < 2.376 is the exponent of matrix multiplication). If one allows randomization, then an (O) over tilde (m(3)n) algorithm is known for this problem. In this paper we present a simple (O) over tilde (m(2)n) randomized algorithm for this problem. The problem of computing a minimum cycle basis in an undirected graph has been well-studied. In this problem a {0, 1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in O(m(2)n + mn(2) logn) time and our randomized algorithm for directed graphs almost matches this running time.

Opportunistic Scheduling in Cellular Systems in the Presence of Noncooperative Mobiles

A central scheduling problem in wireless communications is that of allocating resources to one of many mobile stations that have a common radio channel. Much attention has been given to the design of efficient and fair scheduling schemes that are centrally controlled by a base station (BS) whose decisions depend on the channel conditions reported by each mobile. The BS is the only entity taking decisions in this framework. The decisions are based on the reports of mobiles on their radio channel conditions. In this paper, we study the scheduling problem from a game-theoretic perspective in which some of the mobiles may be noncooperative or strategic, and may not necessarily report their true channel conditions. We model this situation as a signaling game and study its equilibria. We demonstrate that the only Perfect Bayesian Equilibria (PBE) of the signaling game are of the babbling type: the noncooperative mobiles send signals independent of their channel states, the BS simply ignores them, and allocates channels based only on the prior information on the channel statistics. We then propose various approaches to enforce truthful signaling of the radio channel conditions: a pricing approach, an approach based on some knowledge of the mobiles' policies, and an approach that replaces this knowledge by a stochastic approximations approach that combines estimation and control. We further identify other equilibria that involve non-truthful signaling.

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m(3/2)) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n(5/2)) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Omega(n(2)2 root(2lgn)) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Theta (n(2) log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

Optimal MSE solution for a decision feedback equalizer

Due to the inherent feedback in a decision feedback equalizer (DFE) the minimum mean square error (MMSE) or Wiener solution is not known exactly. The main difficulty in such analysis is due to the propagation of the decision errors, which occur because of the feedback. Thus in literature, these errors are neglected while designing and/or analyzing the DFEs. Then a closed form expression is obtained for Wiener solution and we refer this as ideal DFE (IDFE). DFE has also been designed using an iterative and computationally efficient alternative called least mean square (LMS) algorithm. However, again due to the feedback involved, the analysis of an LMS-DFE is not known so far. In this paper we theoretically analyze a DFE taking into account the decision errors. We study its performance at steady state. We then study an LMS-DFE and show the proximity of LMS-DFE attractors to that of the optimal DFE Wiener filter (obtained after considering the decision errors) at high signal to noise ratios (SNR). Further, via simulations we demonstrate that, even at moderate SNRs, an LMS-DFE is close to the MSE optimal DFE. Finally, we compare the LMS DFE attractors with IDFE via simulations. We show that an LMS equalizer outperforms the IDFE. In fact, the performance improvement is very significant even at high SNRs (up to 33%), where an IDFE is believed to be closer to the optimal one. Towards the end, we briefly discuss the tracking properties of the LMS-DFE.

Effects of two-wheelers on saturation flow at signalized intersections in developing countries

Two-wheelers (TW) constitute a major proportion of urban traffic in developing countries and therefore their effect on the saturation flow at signalized intersections could be substantial. This paper attempts to study and analyze the effect of two-wheelers on the saturation flow of signalized intersections by collecting data at a few signalized intersections in Bangalore, India. A strong correlation is observed between the measured saturation flow and the proportion of two-wheeler traffic, which suggest that two-wheelers have significant impact and should be considered in the capacity analysis of signalized intersections. In this paper, the effect of two-wheelers on saturation flow rate is incorporated in a previous model by calibrating and introducing a new adjustment factor for two-wheelers. Results show that saturation flow measured using the modified HCM equation is closer to observed saturation flow values.

Spontaneous formation of branched nanochains from room temperature molten amides: visible and near-IR active, SERS substrates for non-fluorescent and fluorescent analytes

Highly stable, branched gold nanoworms are formed spontaneously in an acetamide-based room temperature molten solvent without any additional external stabilizing or aggregating agent. The nanoworms can be anchored onto solid substrates such as indium tin oxide (ITO) without any change in morphology. The anchored nanoworms are explored as substrates for surface enhanced Raman scattering (SERS) studies using non-fluorescent 4-mercaptobenzoic acid (4-MBA) and fluorescent rhodamine 6G (R6G) as probe molecules. The anchored nanostructured particles respond to near IR (1064 nm) as well as visible (785, 632.8 and 514 nm) excitation lasers and yield good surface enhancement in Raman signals. Enhancement factors of the order 10(6)-10(7) are determined for the analytes using a 1064 nm excitation source. Minimum detection limits based on adsorption from ethanolic solutions of 1028 M 4-MBA and aqueous solutions of 1027 M R6G are achieved. Experimental Raman frequencies and frequencies estimated by DFT calculations are in fairly good agreement. SERS imaging of the nanostructures suggests that the substrates comprising of three dimensional, highly interlinked particles are more suited than particles fused in one dimension. The high SERS activity of the branched nanoworms may be attributed to both electromagnetic and charge transfer effects.

Propyl-2-(8-(3,4-Difluorobenzyl)-2 `,5 `-Dioxo-8-AzaspiroBicyclo3.2.1] Octane-3,4 `-Imidazolidine]-1 `-yl) Acetate Induces Apoptosis in Human Leukemia Cells through Mitochondrial Pathway following Cell Cycle Arrest

Background: Due to the functional defects in apoptosis signaling molecules or deficient activation of apoptosis pathways, leukemia has become an aggressive disease with poor prognosis. Although the majority of leukemia patients initially respond to chemotherapy, relapse is still the leading cause of death. Hence targeting apoptosis pathway would be a promising strategy for the improved treatment of leukemia. Hydantoin derivatives possess a wide range of important biological and pharmacological properties including anticancer properties. Here we investigated the antileukemic activity and mechanism of action of one of the potent azaspiro hydantoin derivative, (ASHD). Materials and Methods: To investigate the antileukemic efficacy of ASHD, we have used MTT assay, cell cycle analysis by FACS, tritiated thymidine incorporation assay, Annexin V staining, JC1 staining and western blot analysis. Results: Results showed that ASHD was approximately 3-fold more potent than the parent compounds in inducing cytotoxicity. Tritiated thymidine assay in conjunction with cell cycle analysis suggests that ASHD inhibited the growth of leukemic cells. The limited effect of ASHD on cell viability of normal cells indicated that it may be specifically directed to cancer cells. Translocation of phosphatidyl serine, activation of caspase 3, caspase 9, PARP, alteration in the ratio of BCL2/BAD protein expression as well as the loss of mitochondrial membrane potential suggests activation of the intrinsic pathway of apoptosis. Conclusion: These results could facilitate the future development of novel hydantoin derivatives as chemotherapeutic agents for leukemia.

Synthesis and evaluation of 2,5-di(4-aryloylaryloxymethyl)-1,3,4-oxadiazoles as anti-cancer agents

A series of 2,5-di(4-aryloylaryloxymethyl)-1,3,4-oxadiazoles 9a-j were obtained via multistep synthesis from hydroxybenzophenones 4a-e. The cytotoxicity of compounds 9a-j was evaluated against human leukemia cell lilies (K562 and CEM). The compounds exhibited moderate to good anti-cancer activity with compounds 9b and 9i having a chloro group exhibiting the best activity (IC50 = 10 mu M). Compound 9i exhibited activity against both the cell lines and 9b only exhibited activity against CEM. Further, a lactate dehydrogenase (LDH) assay and DNA fragmentation studies of the compounds 9a-j were also performed. (C) 2013 Elsevier Masson SAS. All rights reserved.

Fair Scheduling in Cellular Systems in the Presence of Noncooperative Mobiles

We consider the problem of ``fair'' scheduling the resources to one of the many mobile stations by a centrally controlled base station (BS). The BS is the only entity taking decisions in this framework based on truthful information from the mobiles on their radio channel. We study the well-known family of parametric alpha-fair scheduling problems from a game-theoretic perspective in which some of the mobiles may be noncooperative. We first show that if the BS is unaware of the noncooperative behavior from the mobiles, the noncooperative mobiles become successful in snatching the resources from the other cooperative mobiles, resulting in unfair allocations. If the BS is aware of the noncooperative mobiles, a new game arises with BS as an additional player. It can then do better by neglecting the signals from the noncooperative mobiles. The BS, however, becomes successful in eliciting the truthful signals from the mobiles only when it uses additional information (signal statistics). This new policy along with the truthful signals from mobiles forms a Nash equilibrium (NE) that we call a Truth Revealing Equilibrium. Finally, we propose new iterative algorithms to implement fair scheduling policies that robustify the otherwise nonrobust (in presence of noncooperation) alpha-fair scheduling algorithms.

A framework for post-silicon realization of arbitrary instruction extensions on reconfigurable data-paths

In this paper we present a framework for realizing arbitrary instruction set extensions (IE) that are identified post-silicon. The proposed framework has two components viz., an IE synthesis methodology and the architecture of a reconfigurable data-path for realization of the such IEs. The IE synthesis methodology ensures maximal utilization of resources on the reconfigurable data-path. In this context we present the techniques used to realize IEs for applications that demand high throughput or those that must process data streams. The reconfigurable hardware called HyperCell comprises a reconfigurable execution fabric. The fabric is a collection of interconnected compute units. A typical use case of HyperCell is where it acts as a co-processor with a host and accelerates execution of IEs that are defined post-silicon. We demonstrate the effectiveness of our approach by evaluating the performance of some well-known integer kernels that are realized as IEs on HyperCell. Our methodology for realizing IEs through HyperCells permits overlapping of potentially all memory transactions with computations. We show significant improvement in performance for streaming applications over general purpose processor based solutions, by fully pipelining the data-path. (C) 2014 Elsevier B.V. All rights reserved.