The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
With the increasing popularity and development of e-commerce and information technology, multi-attribute bilateral matching problem has been receiving more and more attention. In this paper, multi-attribute bilateral matching problem is discussed based on the consideration of stable matching. Concepts and definitions of multi-attribute bilateral stable matching are presented firstly, followed by the...
Spanning subgraph is necessary for the communication in networks. For example, the malfunctioning of one or more nodes in a network in general affects both the global and the local properties of the remaining nodes, because it makes some edges unusable and destroys the connectivity of the system. In this study, we focus on the characters of a network to be fractional-r-factors, fractional (r, k)-extendable...
We give the first improvement to the space/approximation trade-off of distance oracles since the seminal result of Thorup and Zwick [STOC'01]. For unweighted graphs, our distance oracle has size O(n5/3) = O(n1.66⋯) and, when queried about vertices at distance d, returns a path of length 2d + 1. For weighted graphs with m = n2/α edges, our distance oracle has size O(n2/3√α) and returns a factor 2 approximation...
We present a general method of designing fast approximation algorithms for cut-based minimization problems in undirected graphs. In particular, we develop a technique that given any such problem that can be approximated quickly on trees, allows approximating it almost as quickly on general graphs while only losing a poly-logarithmic factor in the approximation guarantee. To illustrate the applicability...
It is shown that for each t, there is a separator of size O(t√n) in any n-vertex graph G with no Kt-minor. This settles a conjecture of Alon, Seymour and Thomas (J. Amer. Math. Soc, 1990 and STOC'90), and generalizes a result of Djidjev (1981), and Gilbert, Hutchinson and Tarjan (J. Algorithm, 1984), independently, who proved that every graph with n vertices and genus g has a separator of order O(√gn),...
Formal method is an important approach for constructing the trustworthy software. Koch curve is one of the typical fractals graph. A non-recursive algorithm of Koch curve is proposed by employing PAR method and the strategy of developing loop invariant. This algorithm is verified formally. This paper achieves loop invariant of Koch curve with readable, efficient and reliable non-recursive algorithm...
Detecting communities from complex networks has triggered considerable attention in several application domains. Targeting this problem, a local search based genetic algorithm (GALS) which employs a graph-based representation (LAR) has been proposed in this work. The core of the GALS is a local search based mutation technique. Aiming to overcome the drawbacks of the existing mutation methods, a concept...
For an undirected n-vertex planar graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a min st-cut in G? We show how to answer such queries in constant time with O(n log5 n) preprocessing time and O(n log n) space. We use a Gomory-Hu tree to represent all the pairwise min st-cuts implicitly. Previously, no subquadratic...
We present an algorithm that on input of an n-vertex m-edge weighted graph G and a value k, produces an incremental sparsifier G with n-1+m/k edges, such that the condition number of G with G is bounded above by Õ(k log2 n), with probability 1-p. The algorithm runs in time Õ((m log n + n log n) log(1/p)). As a result, we obtain an algorithm that on input of an n × n symmetric diagonally dominant...
Centrality measures are crucial in quantifying the roles and positions of vertices in networks. An important measure is betweenness, which is based on the number of shortest paths that vertices fall on. However, betweenness is computationally expensive to derive, resulting in much research on efficient techniques. We note that in many applications, the key interest is on the high-betweenness vertices...
Currently, community detection has led to a huge interest in data analysis on real-world networks. However, the high computationally demanding of most community detection algorithms limits their applications. In this paper, we propose a heuristic algorithm to extract the community structure in large networks based on local community attractive force optimization whose time complexity is near linear...
Now a days, more and more of social network data are being published in one way or other. So, preserving privacy in publishing social network data has become an important concern. With some local knowledge about individuals in a social network, an adversary may attack the privacy of some victims easily. Most of the work done so far towards privacy preservation can deal with relational data only. However,...
Cluster analysis describes the division of a dataset into subsets of related objects, which are usually disjoint. There is considerable variety among the different types of clustering algorithms. Some of these clustering algorithms represent the dataset as a graph, and use graph-based properties to generate the clusters. However, many graph properties have not been explored as the basis for a clustering...
To find MST (Minimum Spanning Trees) in complete graph is a classical problem in operation research having network design as an important application. It is possible to solve MST problem efficiently, but its Biobjective versions are NP hard. In this paper, we present a comparison of two encoding schemes for representing tree in Biobjective optimization scenario. The three different instances of Biobjective...
Data Grid is a kind of wide-area, distributed storage system, which can provide huge storage capacity. There are millions of files in data grid, distributed in hundreds of geographically dispersed storage resources. Given a unique logical identifier for desired content, replica location service can be used to determine the physical locations of one or more copies of this content. This paper analyzes...
The vast majority of existing route selection processes is designed for vehicle navigation. In this paper we describe an adapted routing algorithm for visually impaired pedestrians based on users needs. Our aim was to find the most adapted route that connects origin and destination points, and which can provide the Blind with a sparse but helpful mental representation of the itinerary and surroundings...
The cooperative shared tele-operation technology is used to overcome the impact of satellite-earth communication delay and non-structural space environment. To get the appropriate collaborative shared teleoperation system operation sequence, the formal based operation strategy is proposed. Firstly, the task sequence algorithm is introduced. In the algorithm, GSPN (generalize stochastic Petri net)...
The dimensions of twisted cubes in the original definition of twisted cubes are only limited to odd integers. In this paper, we first extend the dimensions of twisted cubes to all the positive integers. Then, we introduce the concept of the set of restricted faulty nodes into twisted cubes. We further prove that under the condition that each node of the n-dimensional twisted cube TQn has at least...
Designing appropriate graphs is a problem frequently occurring in several common applications ranging from designing communication and transportation networks to discovering new drugs. More often than not the graphs to be designed need to satisfy multiple, sometimes conflicting, objectives e.g. total length, cost, complexity or other shape and property limitations. In this paper we present our approach...
In this paper, fifteen watershed algorithms are reviewed. For clarity, first we expose two graph exploring methods modified to be guidelines for understanding the approaches taken by these algorithms: the breadth-first watershed and the depth-first watershed. Both paradigms rely on the visiting order applied by the algorithms. The breadth-first is more recognizable as a seed region growing or marker...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.