Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userShortest Paths in Graphs of Convex Sets
162
0
0.0
(
0
)
Added by
Tobia Marcucci Mr.
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a graph, the shortest-path problem requires finding a sequence of edges with minimum cumulative length that connects a source vertex to a target vertex. We consider a generalization of this classical problem in which the position of each vertex in the graph is a continuous decision variable, constrained to lie in a corresponding convex set. The length of an edge is then defined as a convex function of the positions of the vertices it connects. Problems of this form arise naturally in motion planning of autonomous vehicles, robot navigation, and even optimal control of hybrid dynamical systems. The price for such a wide applicability is the complexity of this problem, which is easily seen to be NP-hard. Our main contribution is a strong mixed-integer convex formulation based on perspective functions. This formulation has a very tight convex relaxation and makes it possible to efficiently find globally-optimal paths in large graphs and in high-dimensional spaces.
rate research
Read More
We consider the NP-complete problem of tracking paths in a graph, first introduced by Banik et. al. [3]. Given an undirected graph with a source $s$ and a destination $t$, find the smallest subset of vertices whose intersection with any $s-t$ path results in a unique sequence. In this paper, we show that this problem remains NP-complete when the graph is planar and we give a 4-approximation algorithm in this setting. We also show, via Courcelles theorem, that it can be solved in linear time for graphs of bounded-clique width, when its clique decomposition is given in advance.
Consider a random regular graph with degree $d$ and of size $n$. Assign to each edge an i.i.d. exponential random variable with mean one. In this paper we establish a precise asymptotic expression for the maximum number of edges on the shortest-weight paths between a fixed vertex and all the other vertices, as well as between any pair of vertices. Namely, for any fixed $d geq 3$, we show that the longest of these shortest-weight paths has about $hat{alpha}log n$ edges where $hat{alpha}$ is the unique solution of the equation $alpha log(frac{d-2}{d-1}alpha) - alpha = frac{d-3}{d-2}$, for $alpha > frac{d-1}{d-2}$.
A localized method to distribute paths on random graphs is devised, aimed at finding the shortest paths between given source/destination pairs while avoiding path overlaps at nodes. We propose a method based on message-passing techniques to process global information and distribute paths optimally. Statistical properties such as scaling with system size and number of paths, average path-length and the transition to the frustrated regime are analysed. The performance of the suggested algorithm is evaluated through a comparison against a greedy algorithm.
In this paper we continue the study of the edge intersection graphs of one (or zero) bend paths on a rectangular grid. That is, the edge intersection graphs where each vertex is represented by one of the following shapes: $llcorner$,$ulcorner$, $urcorner$, $lrcorner$, and we consider zero bend paths (i.e., | and $-$) to be degenerate $llcorner$s. These graphs, called $B_1$-EPG graphs, were first introduced by Golumbic et al (2009). We consider the natural subclasses of $B_1$-EPG formed by the subsets of the four single bend shapes (i.e., {$llcorner$}, {$llcorner$,$ulcorner$}, {$llcorner$,$urcorner$}, and {$llcorner$,$ulcorner$,$urcorner$}) and we denote the classes by [$llcorner$], [$llcorner$,$ulcorner$], [$llcorner$,$urcorner$], and [$llcorner$,$ulcorner$,$urcorner$] respectively. Note: all other subsets are isomorphic to these up to 90 degree rotation. We show that testing for membership in each of these classes is NP-complete and observe the expected strict inclusions and incomparability (i.e., [$llcorner$] $subsetneq$ [$llcorner$,$ulcorner$], [$llcorner$,$urcorner$] $subsetneq$ [$llcorner$,$ulcorner$,$urcorner$] $subsetneq$ $B_1$-EPG; also, [$llcorner$,$ulcorner$] is incomparable with [$llcorner$,$urcorner$]). Additionally, we give characterizations and polytime recognition algorithms for special subclasses of Split $cap$ [$llcorner$].
We show that the number of independent sets in cocomparability graphs can be counted in linear time, as can counting cliques in comparability graphs. By contrast, counting cliques in cocomparabilty graphs and counting independent sets in comparability graphs are #P-complete. We extend these results to counting maximal cliques and independent sets. We also consider the fixed-paramet
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
