People who code: we want your input. Take the Survey

# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

944 questions
Filter by
Sorted by
Tagged with
2k views

### All pair shortest path problem for large number of nodes

I am having a small problem. I have the complete city's data which has over 100,000 nodes and 40,000 paths in my database. Now I need to calculate the all pair shortest path between all of them. ...
258 views

### The complexity of the dominating set problem in specific subclasses of chordal graphs

I am interested in the complexity of the dominating set problem (DSP) in some specific graph classes which are subclasses of chordal graphs. A graph is an undirected path graph if it is the vertex-...
235 views

### Complexity of the min edge-colored cut problem

Given an undirected graph $G=(V,E)$ with a color on each edge, the problem is to find a 2-partition $(V_1,V_2)$ of $V$ s.t. the number of colors used by the edges $uv, u \in V_1, v \in V_2$ is ...
105 views

### Evaluate polynomial involving nearly-minimal graph cuts

So you want to evaluate the polynomial $$p(x) = \sum_{C} x^{|C|}$$ where $C$ ranges over all nearly-minimum cuts in a graph (say, all minimal cuts of size $\alpha c$ where $c$ is the edge ...
710 views

### Fastest known algorithm for finding simple paths through given set of vertices

For an undirected graph $G$ and a given set $S$ of vertices, what is the asymptotically fastest known algorithm for finding a simple path containing all elements of $S$. What if we require the path to ...
182 views

### Scaling Algorithms for the Minimum Spanning Tree Problem?

In his paper "Scaling Algorithms for Network Problems", Harold Gabow details several algorithms for graph problems that work using scaling, iteratively refining a candidate answer by beginning with a ...
569 views

### Remove specific edge from ST (link-cut) tree

ST (or link cut) trees are a special kind of trees used for dynamic graph algorithms. They support the following operations in logarithmic time: CUT(v) Deletes the edge from v to its parent JOIN(v, w)...
414 views

### Viapath as a maximum flow problem

Let $G = (V, E)$ be a graph and $a$, $b$, $x$ $\in V \$ different vertices. I have seen stated that the problem of finding a simple path from $a$ to $b$ passing through $x$ can be formulated as a ...
289 views

### Graph connectivity related game [closed]

I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of ...
2k views

### Maximum clique algorithm on undirected graph

Recently I learned about maximum cliques. For fun I came up with an algorithm (described below) to find the maximum cliques in an undirected graph. I'd just like some help constructing a graph s.t. ...
2k views

### Any existing Reeds-Shepp implementations?

Does anyone know of any open source implementations for finding the optimal path of a Reeds-Shepp car? I'm trying to implement the formulas myself, but I'm having trouble with one of them. I think it'...
144 views

### Optimal inlining algorithm

I seek an algorithm to optimise the process of inlinling. Is there such an algorithm, or set of such algorithms? Is there an efficient functional algorithm? To be specific assume we have an Algol ...
324 views

### On Vertex Coloring of Permutation Graph and Comparability Graph and 2-SAT

I have 2 questions. Firstly, I am not sure about differences between Permutaion Graphs and Comparability Graphs. The latter graph class includes the other class. Is there a specific example of graph ...
2k views

### Counting the number of distinct s-t cuts in a oriented graph

I am trying to find the number of distinct s-t cuts in a oriented unweighed graph. In an article Enumeration in Graphs p. 45 I found good way how to enumerate those cuts (section 7.3). Is there a ...
553 views

### Connectivity of graphs by edge and vertex removal

Let us say that a graph $G$ is $(a,b)$-connected if the removal of any $a$ vertices and any $b$ edges from $G$ leaves always a connected graph. For example, a $k$-connected graph, according to the ...
762 views

### Complexity of a switch network problem

A switch network (the name is invented) is made with three types of nodes: one Start node one End node one or more Switch nodes The switch node has 3 exits: Left, Up, Right; has two states L and R ...
320 views

### Early references for discrete optimization

(Apologies if this is misplaced or too broad. I'm open to suggestions on how to reformulate it.) I'm interested in tracing back the "ancient" history of max-flow algorithms, and discrete ...
4k views

### Finding k shortest Paths with Eppstein's Algorithm

I'm trying to figure out how the Path Graph $P(G)$ according to Eppstein's Algorithm in this paper works and how I can reconstruct the $k$ shortest paths from $s$ to $t$ with the corresponding heap ...
744 views

### Clique Enumeration Algorithm

I am reading an old paper of M.C. Golumbic about EPT (edge intersection of paths in a tree) graphs. In the paper it is shown that the number of maximal cliques of an EPT graph instance is polynomial. ...
720 views

### Making a minimum-width tree decomposition lean in polynomial time

As is well known, a tree decomposition of a graph $G$ consists of a tree $T$ with an associated bag $T_v \subseteq V(G)$ for each vertex $v \in V(T)$, which satisfies the following conditions: Every ...
13k views

### Approximation algorithms for Metric TSP

It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time. Is anything known about finding approximation solutions in ...
808 views

### Axioms for Shortest Paths

Suppose we have an undirected weighted graph $G = (V, E, w)$ (with non-negative weights). Let us assume that all shortest paths in $G$ are unique. Suppose we have these $\binom{n}{2}$ paths (sequences ...
549 views

### Capacitated multiple vehicle routing problem with handovers

I'm looking for literature about a variant of the capacitated vehicle/fleet routing problem (a.k.a. VRP, CVRP, etc.) that takes into account the possibility of handovers between multiple vehicles, i.e....
645 views

### Variants of Cluster-Vertex-Deletion problem

The Unweighted Cluster-Vertex-Deletion problem is the following: Input: An undirected graph G = (V, E) and a nonnegative number k Output: Is there a subset X ⊆ V with |X| ≤ k such that deleting all ...
728 views

### Finding min-max vertex-disjoint paths with a common source on planar graphs

Given a planar unweighted graph, and a collection of vertex pairs $(s,t_1),\dots,(s,t_k)$ ($k\ge2$ is a constant), find $k$ vertex-disjoint (except source) paths from $s$ to $t_i$ such that the length ...
337 views

### Connecting cells by line and column permutations in a finite grid

I'd like to know whether the following simple problem has been studied before and if any solution is known. Let G be a finite (MxN) grid, S a subset of G's cells (the "crumbs"). Two crumbs are said ...
2k views

### Path of length k in graph [closed]

I was reading NP complete theory just thought. "Is there any path of length k in given graph" Is it polynomial time algorithm?
1k views

### How should one simulate self-avoiding random walks?

There is a trivial method for simulating a random walk through a graph by exponentiating a stochastic adjacency matrix, but the problem becomes harder if you ask that the random walk be self-avoiding. ...
340 views

### Computing distances with approximation less than 2 in general graphs?

Given a weighted undirected graph with $m = o(n^2)$ edges, I would like to compute distances of approximation less than 2 between any given pair of vertices. Of course, I would like to use ...
2k views

### How to determine whether there is exactly one simple path between two nodes in a graph

Given an undirected sparse graph G and a list of queries (each query consisting of two nodes), how to determine if there exists exactly one simple path between them (for each query) ? I have a (...
2k views

### Data structure for shortest paths

Let $G$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Is it possible to preprocess $G$ and produce a data structure of size $m \cdot \mathrm{polylog}(n)$ so that it can answer ...
484 views

### Is there a constant approximation algorithm for longest path for 3-connected cubic planar graphs or maximal planar graph?

optimization problem Input: a 3-connected cubic planar graph feasible solution: A simple path measure to optimize: length of the simple path Is there a constant approximation algorithm for this ...
801 views

### shortest path algorithm taking into account angular deviation

I am using Floyd-Warshall(1) to compute shortest paths on a road network in order to ultimately compute betweenness centrality of road segments. At present, I am weighting the paths by metric length ...
542 views

### Approximate graph colouring with a promised upper bound on maximum independent set

In my job the following problem arises: Is there a known algorithm, that approximates the chromatic number of a graph without an independent set of order 65? (So alpha(G)<=64 is known and |V|/64 ...
905 views

### Is there fast algorithm for finding min vertex-disjoint path cover of DAG graph of poset of pairs (x, y) where (x, y) < (u, v) iff x < u and y < v

Let P is a poset of pairs (x, y) where (x, y) < (u, v) iff x < u and y < v. Let G is a DAG corresponding to poset P. Suppose I want to find some minimum vertex-disjoint path cover of G. It ...
412 views

### Are there nice generalizations of SPQR trees to k-connected components for k>3?

I'm curious how one should best understand the connections between the k-connected components when $G$ has minimum cuts of size $k>3$, or perhaps approximate minimum cuts produced by Karger's ...
2k views

### Computing the Cheeger constant: feasible for which classes?

Computing the Cheeger constant of a graph, also known as the isoperimetric constant (because it is essentially a minimum area/volume ratio), is known to be NP-complete. Generally it is approximated. ...
2k views

### Sorting points such that the minimal Euclidean distance between consecutive points would be maximized

Given a set of points in a 3D Cartesian space, I am looking for an algorithm that will sort these points, such that the minimal Euclidean distance between two consecutive points would be maximized. ...
197 views

### Algorithm for permuting elements using constant work space

I'm searching for an algorithm to do the following: A 1->3 B 2->6 C 4->5 D 5->2 E 6->4 F 3->7 G 8->9 H 10->11 Elements A-H are stored on ...
382 views

### Finding spanning spiders

Is there a polynomial-time algorithm to find—if one exists—a spanning spider of a given graph $G$? A spider is a tree with at most one node with degree greater than 2:    &...
185 views

### Separation Oracle for Inverse Bipartite Matching Polytope

The $N$x$N$ bipartite matching problem can be written as finding a configuration of variables ${\mathbf y}^* = \{y^*_1, \ldots, y^*_N\}$, $y_i \in \{1, \ldots, N\}$ such that {\mathbf y}^* = \arg\...
242 views

### Two Decision Problems About Graphs — Original Results?

I have a couple of short but pleasing results. I was wondering (a) if they're original (b) if so whom should I tell? I don't have easy access to any standard texts that would help me out here. Nor ...
447 views

### Reducing space usage of st-connectivity with multiple passes?

Suppose a graph $G$ with $n$ vertices is presented as a stream of $m$ edges, but multiple passes are allowed over the stream. Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar Rajagopalan ...
354 views

### On which classes of graphs is resource constrained shortest path (RCSP) NP-hard?

I'm looking to link a problem I'm working on to a known NP-hard problem. I think I can model my problem as a resource constrained shortest path problem. However, the structure of my graph is not ...
346 views

### Recursive parallel topological sorting in linear time

While doing some research on topological sorting I came across a paper Parallel Topological Sorting Algorithm, TADA, A. and MIGITA, M. and NAKAMURA, R. which claims a recursive divide-and-conquer ...
262 views

### Standard format for representing large graphs

I am aware of the "famous" DIMACS graph format (which frankly looks a little clunky to me - "c" for a comment line ?) and the METIS file format. While it's not particularly hard to invent my own ...
89 views

### Resources to get started on fractional graph coloring algorithms

I'm interested in using fractional graph coloring algorithms/solvers to solve a problem, where is a good place to start? I'm looking to find basic/introductory to state-of-the-art algorithms more ...
630 views

### Travelling Salesman and Planar Travel - Generalized TSP

Our beloved Travelling Salesman just bought the Manual of the Planes and wants to make some use of it. He is not a great adventurer though, so he will restrain his travels in the Parallel and ...