331 resultados para Hindi Kavitha


Relevância:

10.00% 10.00%

Publicador:

Resumo:

Given an undirected unweighted graph G = (V, E) and an integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. We present an algorithm with expected running time Õ(m + nk3) for this problem, where |V| = n and |E| = m. Our output is a weighted tree T whose nodes are the sets V1, V2,..., V l of a partition of V, with the property that the edge connectivity in G between any two vertices s ε Vi and t ε Vj, for i ≠ j, is equal to the weight of the lightest edge on the path between Vi and Vj in T. Also, two vertices s and t belong to the same Vi for any i if and only if they have an edge connectivity greater than k. Currently, the best algorithm for this problem needs to compute all-pairs min-cuts in an O(nk) edge graph; this takes Õ(m + n5/2kmin{k1/2, n1/6}) time. Our algorithm is much faster for small values of k; in fact, it is faster whenever k is o(n5/6). Our algorithm yields the useful corollary that in Õ(m + nc3) time, where c is the size of the global min-cut, we can compute the edge connectivities of all those pairs of vertices whose edge connectivity is at most αc for some constant α. We also present an Õ(m + n) Monte Carlo algorithm for the approximate version of this problem. This algorithm is applicable to weighted graphs as well. Our algorithm, with some modifications, also solves another problem called the minimum T-cut problem. Given T ⊆ V of even cardinality, we present an Õ(m + nk3) algorithm to compute a minimum cut that splits T into two odd cardinality components, where k is the size of this cut.

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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.

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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.

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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.

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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).

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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.

Relevância:

10.00% 10.00%

Publicador:

Resumo:

This paper presents the preliminary analysis of Kannada WordNet and the set of relevant computational tools. Although the design has been inspired by the famous English WordNet, and to certain extent, by the Hindi WordNet, the unique features of Kannada WordNet are graded antonyms and meronymy relationships, nominal as well as verbal compoundings, complex verb constructions and efficient underlying database design (designed to handle storage and display of Kannada unicode characters). Kannada WordNet would not only add to the sparse collection of machine-readable Kannada dictionaries, but also will give new insights into the Kannada vocabulary. It provides sufficient interface for applications involved in Kannada machine translation, spell checker and semantic analyser.

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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.

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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.

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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.

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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.

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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.

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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.

Relevância:

10.00% 10.00%

Publicador:

Resumo:

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.