Search

Public transport administrators rely on efficient algorithms for various problems that arise in public transport networks. In particular, our study focused on designing linear-time algorithms for two fundamental path problems: the earliest arrival time (\textsc{eat}) and the fastest path duration (\textsc{fpd}) on public transportation data. We conduct a comparative analysis with state-of-the-art algorithms. The results are quite promising, indicating substantial efficiency improvements. Specifically, the fastest path problem shows a remarkable 34-fold speedup, while the earliest arrival time problem exhibits an even more impressive 183-fold speedup. These findings highlight the effectiveness of our algorithms to solve \textsc{eat} and \textsc{fpd} problems in public transport, and eventually help public administrators to enrich the urban transport experience.

Given a temporal graph G, a source vertex s, and a departure time at source vertex t_s, the earliest arrival time problem EAT is to start from s on or after t_s and reach all the vertices in G as early as possible. Ni et al. have proposed a parallel algorithm for EAT and obtained a speedup up to 9.5 times on real-world graphs with respect to the connection-scan serial algorithm by using multi-core processors. We propose a topology-driven parallel algorithm for EAT on public transport networks and implement using general-purpose programming on the graphics processing unit GPU. A temporal edge or connection in a temporal graph for a public transport network is associated with a departure time and a duration time, and many connections exist from u to v for an edge (u,v). We propose two pruning techniques connection-type and clustering, and use arithmetic progression technique appropriately to process many connections of an edge, without scanning all of them. In the connection-type technique, the connections of an edge with the same duration are grouped together. In the clustering technique, we follow 24-hour format and the connections of an edge are partitioned into 24 clusters so that the departure time of connections in the i^{th} cluster is at least i-hour and at most i+1-hour. The arithmetic progression technique helps to store a sequence of departure times of various connections in a compact way. We propose a hybrid approach to combine the three techniques connection-type, clustering and arithmetic progression in an appropriate way. Our techniques achieve an average speedup up to 59.09 times when compared to the existing connection-scan serial algorithm running on CPU. Also, the average speedup of our algorithm is 12.48 times against the parallel edge-scan-dependency graph algorithm running on GPU.

A semantic net can be used to represent a sentence. A sentence in a language contains semantics which are polar in nature, that is, semantics which are positive, neutral and negative. Neutrosophy is a relatively new field of science which can be used to mathematically represent triads of concepts. These triads include truth, indeterminacy and falsehood, and so also positivity, neutrality and negativity. Thus a conventional semantic net has been extended in this paper using neutrosophy into a Polar Fuzzy Neutrosophic Semantic Net. A Polar Fuzzy Neutrosophic Semantic Net has been implemented in MATLAB and has been used to illustrate a polar sentence in English language. The paper demonstrates a method for the representation of polarity in a computers memory. Thus, polar concepts can be applied to imbibe a machine such as a robot, with emotions, making machine emotion representation possible., Comment: arXiv admin note: text overlap with arXiv:math/0101228, arXiv:math/0412424, arXiv:math/0306384 by other authors

A spanning tree of an unweighted graph is a minimum average stretch spanning tree if it minimizes the ratio of sum of the distances in the tree between the end vertices of the graph edges and the number of graph edges. We consider the problem of computing a minimum average stretch spanning tree in polygonal 2-trees, a super class of 2-connected outerplanar graphs. For a polygonal 2-tree on $n$ vertices, we present an algorithm to compute a minimum average stretch spanning tree in $O(n \log n)$ time. This algorithm also finds a minimum fundamental cycle basis in polygonal 2-trees., Comment: 17 pages, 12 figures

We present a linear time algorithm for computing an implicit linear space representation of a minimum cycle basis (MCB) in weighted partial 2-trees, i.e., graphs of treewidth two. The implicit representation can be made explicit in a running time that is proportional to the size of the MCB. Our algorithm improves the result of Borradaile, Sankowski, and Wulff-Nilsen [Min $st$-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time, FOCS 2010]---which computes for all planar graphs an implicit $O(n \log n)$ space representation of an MCB in $O(n \log^5 n)$ time---by a polylog factor for the special case of partial 2-trees. Such an improvement was achieved previously only for outerplanar graphs [Liu and Lu: Minimum Cycle Bases of Weighted Outerplanar Graphs, IPL 110:970--974, 2010]., Comment: major revision of the paper

For a weighted outerplanar graph, the set of lex short cycles is known to be a minimum cycle basis [Inf. Process. Lett. 110 (2010) 970-974 ]. In this work, we show that the set of lex short cycles is a minimum cycle basis in weighted partial 2-trees (graphs of treewidth two) which is a superclass of outerplanar graphs., Comment: 6 pages, 5 figures

A tree t-spanner of an unweighted graph G is a spanning tree T such that for every two vertices their distance in T is at most t times their distance in G. Given an unweighted graph G and a positive integer t as input, the tree t-spanner problem is to compute a tree t-spanner of G if one exists. This decision problem is known to be NP-complete even in the restricted class of unweighted planar graphs. We present a linear-time reduction from tree t-spanner in outerplanar graphs to the supply-demand tree partition problem. Based on this reduction, we obtain a linear-time algorithm to solve tree t-spanner in outerplanar graphs. Consequently, we show that the minimum value of t for which an input outerplanar graph on n vertices has a tree t-spanner can be found in O(n log n) time.

The paper describes some recent developments in neural networks and discusses the applicability of neural networks in the development of a machine that mimics the human brain. The paper mentions a new architecture, the pulsed neural network that is being considered as the next generation of neural networks. The paper also explores the use of memristors in the development of a brain-like computer called the MoNETA. A new model, multi/infinite dimensional neural networks, are a recent development in the area of advanced neural networks. The paper concludes that the need of neural networks in the development of human-like technology is essential and may be non-expendable for it., Comment: 6 pages, 2 figures

This paper discusses the merits and demerits of crisp logic and fuzzy logic with respect to their applicability in intelligent response generation by a human being and by a robot. Intelligent systems must have the capability of taking decisions that are wise and handle situations intelligently. A direct relationship exists between the level of perfection in handling a situation and the level of completeness of the available knowledge or information or data required to handle the situation. The paper concludes that the use of crisp logic with complete knowledge leads to perfection in handling situations whereas fuzzy logic can handle situations imperfectly only. However, in the light of availability of incomplete knowledge fuzzy theory is more effective but may be disadvantageous as compared to crisp logic., Comment: 4 pages, 1 table

The paper presents a comparison of various soft computing techniques used for filtering and enhancing speech signals. The three major techniques that fall under soft computing are neural networks, fuzzy systems and genetic algorithms. Other hybrid techniques such as neuro-fuzzy systems are also available. In general, soft computing techniques have been experimentally observed to give far superior performance as compared to non-soft computing techniques in terms of robustness and accuracy., Comment: 5 pages