| |
Browse All Reviews > Mathematics Of Computing (G) > Discrete Mathematics (G.2) > Graph Theory (G.2.2) > Path And Circuit Problems (G.2.2...)
|
|
 |
|
|
| |
|
|
| |
1-10 of 20
Reviews about "Path And Circuit Problems (G.2.2...)":
|
Date Reviewed |
| |
Visiting convex regions in a polygonal map
Faigl J., Vonásek V., Přeučil L. Robotics and Autonomous Systems 61(10): 1070-1083, 2013. Type: Article
The multigoal path planning problem (MTP) “is to find a closed shortest path in a polygonal map such that all goals [, which are represented as convex polygons,] are visited.” The problem deals with motion planning,...
|
Apr 9 2014 |
| |
A note on disjoint cycles
Kotrbčík M. Information Processing Letters 112(4): 135-137, 2012. Type: Article
Certain measures of graphs, such as the edge coloring number, are hard to compute precisely. Some others, such as the maximum number of vertex-disjoint cycles, are even hard to approximate. It is known, for example, that computing &...
|
May 17 2012 |
| |
A schedule-based pathfinding algorithm for transit networks using pattern first search
Huang R. Geoinformatica 11(2): 269-285, 2007. Type: Article
The problem of finding the shortest path in a transit network, such as a municipal bus system, is somewhat different from that of finding the shortest path in a road system. In a transit system, buses and trains have routes and transfe...
|
Nov 15 2007 |
| |
Isometric-path numbers of block graphs
Pan J., Chang G. Information Processing Letters 93(2): 99-102, 2005. Type: Article
A problem and solution that arise from a graph-theoretic game called Coppers and Robbers are discussed in this well-written paper. An isometric-path number is related to the number of cops that are needed in the graph to catch a thief....
|
Jul 20 2005 |
| |
 Improved shortest path algorithms for nearly acyclic graphs
Saunders S., Takaoka T. Theoretical Computer Science 293(3): 535-556, 2003. Type: Article
Studied in this interesting paper are fundamental problems that go back 45 years: in a graph G (n vertices, m edges) with positive edge weights, compute the distance to every ver...
|
Sep 4 2003 |
| |
The t-intersection problem in the truncated Boolean lattice: how to write them and why
Ahlswede R., Bey C., Engel K., Khachatrian L. European Journal of Combinatorics 23(5): 471-487, 2002. Type: Article
A family of subsets of X = {1, ... , n} is said to be t-intersecting if |A B| &g...
|
Jun 19 2003 |
| |
Finding the k shortest paths
Eppstein D. SIAM Journal on Computing 28(2): 652-673, 1998. Type: Article
The concern of this paper is a generalization of theshortest path problem, in which not only one but several short pathsmust be produced. More precisely, the k-shortest path problem is to list thek...
|
Jul 1 1999 |
| |
Massively parallel augmenting path algorithms for the assignment problem
Storøy S., Sørevik T. Computing 59(1): 1-16, 1997. Type: Article
The authors present the results of implementing algorithms for the augmenting path problem with dense linear assignments. Two initialization algorithms are parallelized: a naive approach and an initialization based on work by Jonker an...
|
Sep 1 1998 |
| |
Color-coding
Alon N., Yuster R., Zwick U. Journal of the ACM 42(4): 844-856, 1995. Type: Article
A color-coding method in which the vertices of a graph are randomly colored using colors is introduced. The method was originally intended to design algorithms for finding paths ...
|
Jun 1 1996 |
| |
Generating Hamiltonian circuits without backtracking from errors
Shufelt J., Berliner H. Theoretical Computer Science 132(1-2): 347-375, 1994. Type: Article
The knight’s tour problem is as follows: starting with a knight on a square of a chessboard, find a sequence of legal moves that will cause the knight to visit each square exactly once, finally returning to the initial square...
|
Apr 1 1996 |
| |
|
|
| |
|
|
