Search

An original graph-based model and algorithm for optimal industrial task scheduling are proposed in this article. The innovative algorithm designed, dubbed “Dijkstra optimal tasking” (DOT), is suitable for fully distributed task scheduling of autonomous industrial agents for optimal resource allocation, including energy use. The algorithm was designed starting from graph theory fundamentals, from the ground up, to guarantee a generic nature, making it applicable on a plethora of tasking problems and not case-specific. For any industrial setting in which mobile agents are responsible for accomplishing tasks across a site, the objective is to determine the optimal task schedule for each agent, which maximizes the speed of task achievement while minimizing the movement, thereby minimizing energy consumption cost. The DOT algorithm is presented in detail in this manuscript, starting from the conceptualization to the mathematical formulation based on graph theory, having a thorough computational implementation and a detailed algorithm benchmarking analysis. The choice of Dijkstra, as opposed to other shortest path methods (namely, A * Search and Bellman-Ford) in the proposed graph-based model and algorithm, was investigated and justified. An example of a real-world application based on a refinery site is modeled and simulated and the proposed algorithm's effectiveness and computational efficiency are duly evaluated. A dynamic obstacle course was incorporated to effectively demonstrate the proposed algorithm's applicability to real-world applications.

Creating a routing backbone is a fundamental problem in both biology and engineering. The routing backbone of the trail networks of arboreal turtle ants (Cephalotes goniodontus) connects many nests and food sources using trail pheromone deposited by ants as they walk. Unlike species that forage on the ground, the trail networks of arboreal ants are constrained by the vegetation. We examined what objectives the trail networks meet by comparing the observed ant trail networks with networks of random, hypothetical trail networks in the same surrounding vegetation and with trails optimized for four objectives: minimizing path length, minimizing average edge length, minimizing number of nodes, and minimizing opportunities to get lost. The ants’ trails minimized path length by minimizing the number of nodes traversed rather than choosing short edges. In addition, the ants’ trails reduced the opportunity for ants to get lost at each node, favoring nodes with 3D configurations most likely to be reinforced by pheromone. Thus, rather than finding the shortest edges, turtle ant trail networks take advantage of natural variation in the environment to favor coherence, keeping the ants together on the trails., Author summary We investigated the trail networks of arboreal turtle ants in the canopy of the tropical forest, to ask what characterizes the colony’s choice of foraging paths within the vegetation. We monitored day to day changes in the junctions and edges of trail networks of colonies in the dry forest of western Mexico. We compared the paths used by the ants to simulated random paths in the surrounding vegetation. We found that the paths of turtle ants prioritize coherence, keeping ants together on the trail, over minimizing the average edge length. The choice of paths reduces the number of junctions in the trail where ants could get lost, and favors junctions with a physical configuration that makes it likely that successive ants will reinforce the same path. Our work suggests that design principles that emphasize keeping information flow constrained to streamlined, coherent trails may be useful in human-designed distributed routing and transport networks or robot swarms.

Functional connectivity is frequently derived from fMRI data to reduce a complex image of the brain to a graph, or "functional connectome". Often shortest-path algorithms are used to characterize and compare functional connectomes. Previous work on the identification and measurement of semi-metric (shortest circuitous) pathways in the functional connectome has discovered cross-sectional differences in major depressive disorder (MDD), autism spectrum disorder (ASD), and Alzheimer's disease. However, while measurements of shortest path length have been analyzed in functional connectomes, less work has been done to investigate the composition of the pathways themselves, or whether the edges composing pathways differ between individuals. Developments in this area would help us understand how pathways might be organized in mental disorders, and if a consistent pattern can be found. Furthermore, studies in structural brain connectivity and other real-world graphs suggest that shortest pathways may not be as important in functional connectivity studies as previously assumed. In light of this, we present a novel measurement of the consistency of pathways across functional connectomes, and an algorithm for improvement by selecting the most frequently occurring "normative pathways" from the k shortest paths, instead of just the shortest path. We also look at this algorithm's effect on various graph measurements, using randomized matrix simulations to support the efficacy of this method and demonstrate our algorithm on the resting-state fMRI (rs-fMRI) of a group of 34 adolescent control participants. Additionally, a comparison of normative pathways is made with a group of 82 age-matched participants, diagnosed with MDD, and in doing so we find the normative pathways that are most disrupted. Our results, which are carried out with estimates of connectivity derived from correlation, partial correlation, and normalized mutual information connectomes, suggest disruption to the default mode, affective, and ventral attention networks. Normative pathways, especially with partial correlation, make greater use of critical anatomical pathways through the striatum, cingulum, and the cerebellum. In summary, MDD is characterized by a disruption of normative pathways of the ventral attention network, increases in alternative pathways in the frontoparietal network in MDD, and a mixture of both in the default mode network. Additionally, within- and between-groups findings depend on the estimate of connectivity.

Graph theory has been extensively applied to investigate complex brain networks in current neuroscience research. Many metrics derived from graph theory, such as local and global efficiencies, are based on the path length between nodes. These approaches are commonly used in analyses of brain networks assessed by resting-state functional magnetic resonance imaging, although relying on the strong assumption that information flow throughout the network is restricted to the shortest paths. In this study, we propose the utilization of commute time as a tool to investigate regional centrality on the functional connectome. Our initial hypothesis was that an alternative approach that considers alternative routes (such as commute time) could provide further information into the organization of functional networks. However, our empirical findings on the ADHD-200 database suggest that at the group level, the commute time and shortest path are highly correlated. In contrast, at the subject level, we discovered that commute time is much less susceptible to head motion artifacts when compared with metrics based on shortest paths. Given the overall similarity between the measures, we argue that commute time might be advantageous particularly for connectomic studies in populations where motion artifacts are a major issue.

We investigated the influence of processing steps in the estimation of multivariate directed functional connectivity during seizures recorded with intracranial EEG (iEEG) on seizure-onset zone (SOZ) localization. We studied the effect of (i) the number of nodes, (ii) time-series normalization, (iii) the choice of multivariate time-varying connectivity measure: Adaptive Directed Transfer Function (ADTF) or Adaptive Partial Directed Coherence (APDC) and (iv) graph theory measure: outdegree or shortest path length. First, simulations were performed to quantify the influence of the various processing steps on the accuracy to localize the SOZ. Afterwards, the SOZ was estimated from a 113-electrodes iEEG seizure recording and compared with the resection that rendered the patient seizure-free. The simulations revealed that ADTF is preferred over APDC to localize the SOZ from ictal iEEG recordings. Normalizing the time series before analysis resulted in an increase of 25–35% of correctly localized SOZ, while adding more nodes to the connectivity analysis led to a moderate decrease of 10%, when comparing 128 with 32 input nodes. The real-seizure connectivity estimates localized the SOZ inside the resection area using the ADTF coupled to outdegree or shortest path length. Our study showed that normalizing the time-series is an important pre-processing step, while adding nodes to the analysis did only marginally affect the SOZ localization. The study shows that directed multivariate Granger-based connectivity analysis is feasible with many input nodes (> 100) and that normalization of the time-series before connectivity analysis is preferred. Electronic supplementary material The online version of this article (10.1007/s10548-018-0646-7) contains supplementary material, which is available to authorized users.

We answer Bryant's combinatorial challenge on minimal walks of phylogenetic treespace under the nearest-neighbor interchange (NNI) metric. We show that the shortest path through the NNI-treespace of $(n)$-leaf trees is Hamiltonian for all $(n)$. That is, there is a minimal path that visits all binary trees exactly once, under NNI moves.

Computing the shortest path, overcoming obstacles in a plane, is a well-known geometric problem. However, widely assumed obstacles are polygonal in nature. Very few papers have focused on curved obstacles, and in particular, for curved multiply-connected domains (domains having holes). Given a set of parametric curves forming a multiply-connected domain (MCD), with one closed curve acting as an outer boundary and several non-intersecting inner curves (loops) as representing holes and two distinct points S and E lying on the outer boundary, this paper provides an algorithm to find the shortest interior path (SIP) between the two points in the domain. SIP consists of portions of curves along with straight line segments that are tangential to the curve. The algorithm initially computes point-curve tangents (PCTs) and bitangents (BTs) using their respective constraints. A generalized region lemma is proposed, which is then employed to remove PCTs/BTs that will not contribute to the potential path and subsequently aiding in removing a few inner loops. The algorithm is designed to explore all potential paths. Merging of paths is also proposed to avoid redundant computations. A final SIP is chosen from potential paths using the length of each path. The algorithm also has the potential to give all paths of equal lengths contributing to shortest paths (within a tolerance level). As the algorithm computes all the potential paths on the fly, there is no need to employ a visibility graph to compute the shortest path. Curves are represented using non-uniform rational B-splines (NURBS). The algorithm uses the curves as such and does not discretize into point-sets or polygons. Extensions to handle curves with C1 discontinuities and S and E not on the outer boundary have also been described. Results of the implementation are provided and complexity of the algorithm is also discussed. This paper follows up the one presented for simply-connected domains (SCDs) in Bharath Ram and Ramanathan (2011) [4]. � 2012 Elsevier Ltd. All rights reserved.

We introduce a metric in graph search and demonstrate its application for segmenting retinal optical coherence tomography (OCT) images of macular pathology. Our proposed “adjusted mean arc length” (AMAL) metric is an adaptation of the lowest mean arc length search technique for automated OCT segmentation. We compare this method to Dijkstra’s shortest path algorithm, which we utilized previously in our popular graph theory and dynamic programming segmentation technique. As an illustrative example, we show that AMAL-based length-adaptive segmentation outperforms the shortest path in delineating the retina/vitreous boundary of patients with full-thickness macular holes when compared with expert manual grading.

Recently, the number of studies involving complex network applications in transportation has increased steadily as scholars from various fields analyze traffic networks. Nonetheless, research on rail network growth is relatively rare. This research examines the evolution of the Public Urban Rail Transit Networks of Kuala Lumpur (PURTNoKL) based on complex network theory and covers both the topological structure of the rail system and future trends in network growth. In addition, network performance when facing different attack strategies is also assessed. Three topological network characteristics are considered: connections, clustering and centrality. In PURTNoKL, we found that the total number of nodes and edges exhibit a linear relationship and that the average degree stays within the interval [2.0488, 2.6774] with heavy-tailed distributions. The evolutionary process shows that the cumulative probability distribution (CPD) of degree and the average shortest path length show good fit with exponential distribution and normal distribution, respectively. Moreover, PURTNoKL exhibits clear cluster characteristics; most of the nodes have a 2-core value, and the CPDs of the centrality's closeness and betweenness follow a normal distribution function and an exponential distribution, respectively. Finally, we discuss four different types of network growth styles and the line extension process, which reveal that the rail network's growth is likely based on the nodes with the biggest lengths of the shortest path and that network protection should emphasize those nodes with the largest degrees and the highest betweenness values. This research may enhance the networkability of the rail system and better shape the future growth of public rail networks.

In this paper, a new self-organizing map (SOM) based adaptation procedure is proposed to address the multiple watchman route problem with the restricted visibility range in the polygonal domain W. A watchman route is represented by a ring of connected neuron weights that evolves in W, while obstacles are considered by approximation of the shortest path. The adaptation procedure considers a coverage of W by the ring in order to attract nodes toward uncovered parts of W. The proposed procedure is experimentally verified in a set of environments and several visibility ranges. Performance of the procedure is compared with the decoupled approach based on solutions of the art gallery problem and the consecutive traveling salesman problem. The experimental results show the suitability of the proposed procedure based on relatively simple supporting geometrical structures, enabling application of the SOM principles to watchman route problems in W.

Transportation networks are subject to significant travel time uncertainty as a result of traveler behavior, recurring congestion, capacity variability (construction zones, traffic incidents), variation in demand, and so on. Therefore, interest is growing in modeling and optimizing travel time reliability in such networks. This paper proposes an efficient algorithm to compute the path of maximum travel time reliability on a network with normally distributed and correlated link travel times. For this optimal reliability path (ORP) problem, it is shown that the subpath optimality condition for the deterministic shortest path problem does not hold, and consequently, a new bounds-based optimality criterion is proposed using the K shortest expected time paths and the minimum path variance on the network. An algorithm is developed to solve the ORP problem on the basis of the proposed optimality criterion and an efficient path generation procedure. Computational experiments on various test networks show the proposed algorithm to be efficient, requiring limited path enumeration. With as few as five shortest paths and 50 Monte Carlo draws, the proposed algorithm is able to find the most reliable path for realistic network sizes. Empirical investigations highlight the unreliability of the least expected time path and suboptimality of the independence assumption. The study also underscores the role of risk attitudes (reflected by reliability threshold) on the benefits of the ORP. The algorithm and empirical results have important applications for developing reliability-based routing applications for congestion mitigation and intelligent transportation systems.

In this paper, we propose a multi-layered data association scheme with graph-theoretic formulation for tracking multiple objects that undergo switching dynamics in clutter. The proposed scheme takes as input object candidates detected in each frame. At the object candidate level, "tracklets" are "grown" from sets of candidates that have high probabilities of containing only true positives. At the tracklet level, a directed and weighted graph is constructed, where each node is a tracklet, and the edge weight between two nodes is defined according to the "compatibility'' of the two tracklets. The association problem is then formulated as an all-pairs shortest path (APSP) problem in this graph. Finally, at the path level, by analyzing the all-pairs shortest paths, all object trajectories are identified, and track initiation and track termination are automatically dealt with. By exploiting a special topological property of the graph, we have also developed a more efficient APSP algorithm than the general-purpose ones. The proposed data association scheme is applied to tennis sequences to track tennis balls. Experiments show that it works well on sequences where other data association methods perform poorly or fail completely.

The representation of a genome by oligonucleotide probes is a prerequisite for the analysis of many of its basic properties, such as transcription factor binding sites, chromosomal breakpoints, gene expression of known genes and detection of novel genes, in particular those coding for small RNAs. An ideal representation would consist of a high density set of oligonucleotides with similar melting temperatures that do not cross-hybridize with other regions of the genome and are equidistantly spaced. The implementation of such design is typically called a tiling array or genome array. We formulate the minimal cost tiling path problem for the selection of oligonucleotides from a set of candidates. Computing the selection of probes requires multi-criterion optimization, which we cast into a shortest path problem. Standard algorithms running in linear time allow us to compute globally optimal tiling paths from millions of candidate oligonucleotides on a standard desktop computer for most problem variants. The solutions to this multi-criterion optimization are spatially adaptive to the problem instance. Our formulation incorporates experimental constraints with respect to specific regions of interest and trade offs between hybridization parameters, probe quality and tiling density easily. A web application is available at http://tileomatic.org.

Advances in the field of genomics have enabled computational analysis of metabolic pathways at the genome scale. Singular attention has been devoted in the literature to stoichiometric approaches, and path-finding approaches, to metabolic pathways. Stoichiometric approaches make use of reaction stoichiometry when trying to determine metabolic pathways. Stoichiometric approaches involve elementary flux modes and extreme pathways. In contrast, path-finding approaches propose an alternative view based on graph theory in which reaction stoichiometry is not considered. Path-finding approaches use shortest path and k-shortest path concepts. In this article we give a critical overview of the theory, applications and key research challenges of stoichiometric and path-finding approaches to metabolic pathways.

This paper presents several results on some cost-minimizing path problems in polygonal regions. For these types of problems, an approach often used to compute approximate optimal paths is to apply a discrete search algorithm to a graph G(epsilon) constructed from a discretization of the problem; this graph is guaranteed to contain an epsilon-good approximate optimal path, i.e., a path with a cost within (1 + epsilon) factor of that of an optimal path, between given source and destination points. Here, epsilon0 is the user-defined error tolerance ratio. We introduce a class of piecewise pseudo-Euclidean optimal path problems that includes several non-Euclidean optimal path problems previously studied and show that the BUSHWHACK algorithm, which was formerly designed for the weighted region optimal path problem, can be generalized to solve any optimal path problem of this class. We also introduce an empirical method called the adaptive discretization method that improves the performance of the approximation algorithms by placing discretization points densely only in areas that may contain optimal paths. It proceeds in multiple iterations, and in each iteration, it varies the approximation parameters and fine tunes the discretization.

The recognition community has typically avoided bridging the representational gap between traditional, low-level image features and generic models. Instead, the gap has been artificially eliminated by either bringing the image closer to the models using simple scenes containing idealized, textureless objects or by bringing the models closer to the images using 3D CAD model templates or 2D appearance model templates. In this paper, we attempt to bridge the representational gap for the domain of model acquisition. Specifically, we address the problem of automatically acquiring a generic 2D view-based class model from a set of images, each containing an exemplar object belonging to that class. We introduce a novel graph-theoretical formulation of the problem in which we search for the lowest common abstraction among a set of lattices, each representing the space of all possible region groupings in a region adjacency graph representation of an input image. The problem is intractable and we present a shortest path-based approximation algorithm to yield an efficient solution. We demonstrate the approach on real imagery.

This paper presents a fully automated algorithm to segment fluid-associated (fluid-filled) and cyst regions in optical coherence tomography (OCT) retina images of subjects with diabetic macular edema. The OCT image is segmented using a novel neutrosophic transformation and a graph-based shortest path method. In neutrosophic domain, an image $g$ is transformed into three sets: $T$ (true), $I$ (indeterminate) that represents noise, and $F$ (false). This paper makes four key contributions. First, a new method is introduced to compute the indeterminacy set $I$ , and a new $\lambda$ -correction operation is introduced to compute the set $T$ in neutrosophic domain. Second, a graph shortest-path method is applied in neutrosophic domain to segment the inner limiting membrane and the retinal pigment epithelium as regions of interest (ROI) and outer plexiform layer and inner segment myeloid as middle layers using a novel definition of the edge weights . Third, a new cost function for cluster-based fluid/cyst segmentation in ROI is presented which also includes a novel approach in estimating the number of clusters in an automated manner. Fourth, the final fluid regions are achieved by ignoring very small regions and the regions between middle layers. The proposed method is evaluated using two publicly available datasets: Duke, Optima, and a third local dataset from the UMN clinic which is available online. The proposed algorithm outperforms the previously proposed Duke algorithm by 8% with respect to the dice coefficient and by 5% with respect to precision on the Duke dataset, while achieving about the same sensitivity. Also, the proposed algorithm outperforms a prior method for Optima dataset by 6%, 22%, and 23% with respect to the dice coefficient, sensitivity, and precision, respectively. Finally, the proposed algorithm also achieves sensitivity of 67.3%, 88.8%, and 76.7%, for the Duke, Optima, and the university of minnesota (UMN) datasets, respectively.

Summary: Rapidly increasing amounts of molecular interaction data are being produced by various experimental techniques and computational prediction methods. In order to gain insight into the organization and structure of the resultant large complex networks formed by the interacting molecules, we have developed the versatile Cytoscape plugin NetworkAnalyzer. It computes and displays a comprehensive set of topological parameters, which includes the number of nodes, edges, and connected components, the network diameter, radius, density, centralization, heterogeneity, and clustering coefficient, the characteristic path length, and the distributions of node degrees, neighborhood connectivities, average clustering coefficients, and shortest path lengths. NetworkAnalyzer can be applied to both directed and undirected networks and also contains extra functionality to construct the intersection or union of two networks. It is an interactive and highly customizable application that requires no expert knowledge in graph theory from the user. Availability: NetworkAnalyzer can be downloaded via the Cytoscape web site: http://www.cytoscape.org Contact: mario.albrecht@mpi-inf.mpg.de Supplementary information: Supplementary data are available at Bioinformatics online.

Several studies have been made in finding the faces of an object depicted in a line drawing, but the problem has not been completely solved. Although existing methods can find the correct faces in most cases, there is no mechanism to ascertain that they are indeed correct, leaving the human user to do so. This paper uses a two-stage approach--find potential faces, then validate their correctness--to ensure that only correct faces are delivered ultimately. The face finding itself uses a double breadth-first search algorithm, which yields the shortest path, to find the potential faces. The basic premise is that the smallest faces found are more likely the correct ones. They serve as the "seed" potential faces, from which the algorithm proceeds to search for more faces. If the potential faces found satisfy the validation rules, then they are accepted as correct. Otherwise, the wrong potential faces are identified and removed, and new ones found in their place. The validation process is then repeated. The algorithm is fast and reliable, can deal with planar-faced manifold and nonmanifold objects, and can deliver the different results when a drawing has multiple interpretations. Our extensive tests show that the method can deal with most cases efficiently, including those that previous methods cannot solve.

To study the differences in functional brain networks between eyes-closed (EC) and eyes-open (EO) at resting state, electroencephalographic (EEG) activity was recorded in 21 normal adults during EC and EO states. The synchronization likelihood (SL) was applied to measure correlations between all pairwise EEG channels, and then the SL matrices were converted to graphs by thresholding. Graphs were measured by topological parameters in theta (4–7 Hz), alpha (8–13 Hz), and beta (14–30 Hz) bands. By changing from EC to EO states, mean cluster coefficients decreased in both theta and alpha bands, but mean shortest path lengths became shorter only in the alpha band. In addition, local efficiencies decreased in both theta and alpha bands, while global efficiencies in the alpha band increased inversely. Opening the eyes decreased both nodes and connections in frontal area in the theta band, and also decreased those in bilateral posterior areas in the alpha band. These results suggested that a combination of the SL and graph theory methods may be a useful tool for distinguishing states of EC and EO. The differences in functional connectivity between EC and EO states may reflect the difference of information communication in human brain.

Bootstrap methods have recently been introduced to diffusion-weighted magnetic resonance imaging to estimate the measurement uncertainty of ensuing diffusion parameters directly from the acquired data without the necessity to assume a noise model. These methods have been previously combined with deterministic streamline tractography algorithms to allow for the assessment of connection probabilities in the human brain. Thereby, the local noise induced disturbance in the diffusion data is accumulated additively due to the incremental progression of streamline tractography algorithms. Graph based approaches have been proposed to overcome this drawback of streamline techniques. For this reason, the bootstrap method is in the present work incorporated into a graph setup to derive a new probabilistic fiber tractography method, called BootGraph. The acquired data set is thereby converted into a weighted, undirected graph by defining a vertex in each voxel and edges between adjacent vertices. By means of the cone of uncertainty, which is derived using the wild bootstrap, a weight is thereafter assigned to each edge. Two path finding algorithms are subsequently applied to derive connection probabilities. While the first algorithm is based on the shortest path approach, the second algorithm takes all existing paths between two vertices into consideration. Tracking results are compared to an established algorithm based on the bootstrap method in combination with streamline fiber tractography and to another graph based algorithm. The BootGraph shows a very good performance in crossing situations with respect to false negatives and permits incorporating additional constraints, such as a curvature threshold. By inheriting the advantages of the bootstrap method and graph theory, the BootGraph method provides a computationally efficient and flexible probabilistic tractography setup to compute connection probability maps and virtual fiber pathways without the drawbacks of streamline tractography algorithms or the assumption of a noise distribution. Moreover, the BootGraph can be applied to common DTI data sets without further modifications and shows a high repeatability. Thus, it is very well suited for longitudinal studies and meta-studies based on DTI.

We investigate the problem of solving traditional combinatorial graph problems using secure multi-party computation techniques, focusing on the shortest path and the maximum flow problems. To the best of our knowledge, this is the first time these problems have been addressed in a general multi-party computation setting. Our study highlights several complexity gaps and suggests the exploration of various trade-offs, while also offering protocols that are efficient enough to solve real-world problems.

In this thesis we study problems from real situations, which can be applied to network graphs and solved using mathematical graph theory. We start with the problem of oriented network design. The problem originates from networks, where the flow over the arcs is important and many times limited with the capacity of the networks. There are several techniques and results on the problem of assigning the flow through the network channels. In our problem, we try to find the optimal network structure, which could be used in the design phase of the network. With metaheuristics, we search for optimal network structures for a given number of nodes. We define triangle neighborhood and compare the results of the algorithm with the conjecture by Choplin et al. [8]. Further, we study the problem of order picking and order batching in block structured warehouses. For order picking problem, we present the extension of a dynamic programming algorithm by Ratliff and Rosenthal [42], which enables the development of an algorithm for an unlimited number of blocks. In order to achieve this, a new presentation of states and transitions of dynamic programming algorithm is given. We prove that the resulting path is optimal for the given structure. We compare the optimal path lengths to the results found in literature and also investigate the impact of warehouse layout parameters onto the routing. Closely related to the problem of order picking, we investigate the order batching problem. We discuss the variation of the order batching problem with time windows and present the algorithmic approach to solving the problem. The previously presented optimal path algorithm is applied in the algorithm to ensure even better quality of results. We introduce the evaluation function of a batch and compare the results of the algorithm with the test data from the literature as well as with data from the real warehouse. We conclude by summarizing the results and stating some possible extensions and further work. V doktorskem delu smo preučili problem iz vsakdanjih situacij, ki jih je mogoče prevesti na problem na omrežnih grafih in jih rešili z uporabo matematične teorije grafov. Začnemo s problemom usmerjenih omrežij. Problem izvira iz omrežja, kjer je pretok skozi loke pomemben in velikokrat omejen s kapaciteto omrežij. Obstaja več tehnik ter rezultatov za problem določanja pretoka skozi omrežja. Pri našem problemu poskušamo najti optimalno omrežno strukturo, ki bi se lahko uporabljala v fazi načrtovanja omrežja. Z metahevrističnim pristopom iščemo optimalne strukture omrežja za določeno število vozlišč. Definiramo trikotniško soseščino in primerjamo rezultate algoritma z domnevo, ki so jo postavili Choplin in drugi. Nadalje preučujemo problem iskanja optimalne poti v bločno strukturiranem skladišču. Za problem predstavimo nadgradnjo algoritma dinamičnega programiranja, ki sta ga uvedla Ratliff in Rosenthal, in ki omogoča razvoj algoritma za neomejeno število blokov. Predstavljen je nov način zapisa stanja in prehodov med fazami dinamičnega programiranja. Dokažemo, da je rezultantna pot optimalna. Primerjamo naše rezultate za dolžino optimalne poti z rezultati iz literature in preučimo vpliv parametrov na najkrajše poti pri različnih postavitvah skladišč. Preučimo še tesno povezan problem komisioniranja, in sicer različico z časovnimi okni. Predstavimo algoritmični pristop k reševanju problema. Uporabimo predhodno predstavljen algoritem za iskanje optimalne poti,in s tem zagotovimo še večjo kakovost rezultatov. Uvedemo ocenitveno funkcijo za množico naročil in primerjamo rezultate algoritma s podatki iz literature, kot tudi s podatki iz dejanskega skladišča. Delo zaključimo s povzetkom rezultatov in navedemo nekatere možne razširitve in nadgradnje.

Given two distinct points S and E on a closed parametric curve forming the boundary of a simply-connected domain (without holes), this paper provides an algorithm to find the shortest interior path (SIP) between the two points in the domain. The SIP consists of portions of curves along with straight line segments that are tangential to the curve. The algorithm initially computes point-curve tangents and bitangents using their respective constraints. They are then analyzed further to identify potential tangents. A region check is performed to determine the tangent that will form part of the SIP. Portions of the curve that belong to the SIP are also identified during the process. The SIP is identified without explicitly computing the length of the curves/tangents. The curve is represented using non-uniform rational B-splines (NURBS). Results of the implementation are provided. � 2011 Elsevier Ltd. All rights reserved.

Comparing and computing distances between phylogenetic trees are important biological problems, especially for models where edge lengths play an important role. The geodesic distance measure between two phylogenetic trees with edge lengths is the length of the shortest path between them in the continuous tree space introduced by Billera, Holmes, and Vogtmann. This tree space provides a powerful tool for studying and comparing phylogenetic trees, both in exhibiting a natural distance measure and in providing a euclidean-like structure for solving optimization problems on trees. An important open problem is to find a polynomial time algorithm for finding geodesics in tree space. This paper gives such an algorithm, which starts with a simple initial path and moves through a series of successively shorter paths until the geodesic is attained.

International audience; We recently introduced the watershed cuts, a notion of watershed in edge-weighted graphs. In this paper, our main contribution is a thinning paradigm from which we derive three algorithmic watershed cut strategies: the first one is well suited to parallel implementations, the second one leads to a flexible linear-time sequential implementation whereas the third one links the watershed cuts and the popular flooding algorithms. We state that watershed cuts preserve a notion of contrast, called connection value, on which are (implicitly) ased several morphological region merging methods. We also establish the links and differences between watershed cuts, minimum spanning forests, shortest-path forests and topological watersheds. Finally, we present illsutrations of the proposed framework to the segmentation of artwork surfaces and diffusion tensor images.

Shortest paths have been used to segment object boundaries with both continuous and discrete image models. Although these techniques are well defined in 2D, the character of the path as an object boundary is not preserved in 3D. An object boundary in three dimensions is a 2D surface. However, many different extensions of the shortest path techniques to 3D have been previously proposed in which the 3D object is segmented via a collection of shortest paths rather than a minimal surface, leading to a solution which bears an uncertain relationship to the true minimal surface. Specifically, there is no guarantee that a minimal path between points on two closed contours will lie on the minimal surface joining these contours. We observe that an elegant solution to the computation of a minimal surface on a cellular complex (e.g., a 3D lattice) was given by Sullivan [47]. Sullivan showed that the discrete minimal surface connecting one or more closed contours may be found efficiently by solving a Minimum-cost Circulation Network Flow (MCNF) problem. In this work, we detail why a minimal surface properly extends a shortest path (in the context of a boundary) to three dimensions, present Sullivan's solution to this minimal surface problem via an MCNF calculation, and demonstrate the use of these minimal surfaces on the segmentation of image data.

Restoration of writing order from a single-stroked handwriting image can be seen as the problem of finding the smoothest path in its graph representation. In this paper, a 3-phase approach to restore a writing order is proposed within the framework of the Edge Continuity Relation (ECR). In the initial, local phase, in order to obtain possible ECRs at an even-degree node, a neural network is used for the node of degree 4 and a theoretical approach is presented for the node of degree higher than 4 by introducing certain reasonable assumptions. In the second phase, we identify double-traced lines by employing maximum weighted matching. This makes it possible to transform the problem of obtaining possible ECRs at odd-degree node to that at even-degree node. In the final, global phase, we find all the candidates of single-stroked paths by depth first search and select the best one by evaluating SLALOM smoothness. Experiments on static images converted from online data in the Unipen database show that our method achieves a restoration rate of 96.0 percent.

This paper presents a simple yet efficient dynamic-programming (DP) shortest path algorithm for real-time collision-free robot-path planning applicable to situations in which targets and barriers are permitted to move. The algorithm works in real time and requires no prior knowledge of target or barrier movements. In the case that the barriers are stationary, this paper proves that this algorithm always results in the robot catching the target, provided it moves at a greater speed than the target, and the dynamic-system update frequency is sufficiently large. Like most robot-path-planning approaches, the environment is represented by a topologically organized map. Each grid point on the map has only local connections to its neighboring grid points from which it receives information in real time. The information stored at each point is a current estimate of the distance to the nearest target and the neighbor from which this distance was determined. Updating the distance estimate at each grid point is done using only the information gathered from the point's neighbors, that is, each point can be considered an independent processor, and the order in which grid points are updated is not determined based on global knowledge of the current distances at each point or the previous history of each point. The robot path is determined in real time completely from the information at the robot's current grid-point location. The computational effort to update each point is minimal, allowing for rapid propagation of the distance information outward along the grid from the target locations. In the static situation, where both the targets and the barriers do not move, this algorithm is a DP solution to the shortest path problem, but is restricted by lack of global knowledge. In this case, this paper proves that the dynamic system converges in a small number of iterations to a state where the minimal distance to a target is recorded at each grid point and shows that this robot-path-planning algorithm can be made to always choose an optimal path. The effectiveness of this algorithm is demonstrated through a number of simulations.

Our knowledge of metabolism can be represented as a network comprising several thousands of nodes (compounds and reactions). Several groups applied graph theory to analyse the topological properties of this network and to infer metabolic pathways by path finding. This is, however, not straightforward, with a major problem caused by traversing irrelevant shortcuts through highly connected nodes, which correspond to pool metabolites and co-factors (e.g. H2O, NADP and H+). In this study, we present a web server implementing two simple approaches, which circumvent this problem, thereby improving the relevance of the inferred pathways. In the simplest approach, the shortest path is computed, while filtering out the selection of highly connected compounds. In the second approach, the shortest path is computed on the weighted metabolic graph where each compound is assigned a weight equal to its connectivity in the network. This approach significantly increases the accuracy of the inferred pathways, enabling the correct inference of relatively long pathways (e.g. with as many as eight intermediate reactions). Available options include the calculation of the k-shortest paths between two specified seed nodes (either compounds or reactions). Multiple requests can be submitted in a queue. Results are returned by email, in textual as well as graphical formats (available in http://www.scmbb.ulb.ac.be/pathfinding/)., Journal Article, Research Support, Non-U.S. Gov't, Validation Studies, info:eu-repo/semantics/published

The dynamic generation and qualitative analysis of metabolic networks relying on continuously growing qualified metabolic data by a joint database/graph theoretical approach is described. The procedure is applied to analyze the connectivity of a metabolic network after enzyme removal and to subsequently perform shortest path analyses. The focus lies on the analysis of the connectivity of the metabolic network depending on model assumptions. Here we analyze the influence of the number of strongly connected components on the assignment of reversibility or irreversibility of the biochemical reactions.

Cataloged from PDF version of article. A shortest-route formulation of the mixed-model assembly line balancing problem is presented. Common tasks across models are assumed to exist and these tasks are performed in the same stations. The formulation is based on an algorithm which solves the single-model version of the problem. The mixed-model system is transformed into a singlemodel system with a combined precedence diagram. The model is capable of considering any constraint that can be expressed as a function of task assignments. Ó 1999 Elsevier Science B.V. All rights reserved.

We propose a path-based framework for deriving and simplifying source-tracking information for first-order term unification in the empty theory. Such a framework is useful for diagnosing unification-based systems, including debugging of type errors in programs and the generation of success and failure proofs in logic programming. The objects of source-tracking are deductions in the logic of term unification. The semantics of deductions are paths over a unification graph whose labels form the suffix language of a semi-Dyck set. Based on this idea of unification paths, two algorithms for generating proofs are presented: the first uses context-free labeled shortest-path algorithms to generate optimal (shortest) proofs in time O(n3) for a fixed signature, where n is the number of vertices of the unification graph. The second algorithm integrates easily with standard unification algorithms, entailing an overhead of only a constant factor, but generates non-optimal proofs. These non-optimal proofs may be further simplified by group rewrite rules.