# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

951 questions
Filter by
Sorted by
Tagged with
593 views

### Exact Algorithm for edge labeling problem in DAG

I am implementing some system part of which requires some help. I am therefore framing it as a graph problem to make it domain independent. Problem: We are given directed acyclic graph $G=(V,E)$. ...
1k views

### Edge-weight updates in all pair shortest path problem

I want to calculate all-pairs shortest paths on a graph with roughly 50,000 nodes representing a city-wide road network. An answer to my previous question led me to Hiroki Yanagisawa's paper "A multi-...
2k views

### Finding triangles in a graph: other approaches besides property testing?

We're working on a paper that presents some algorithms for finding triangles and network motifs (constant size subgraphs, also known as graphlets) in a distributed setting. We characterize the ...
342 views

### Max-Cut Of Minor Closed Family

It's well known that planar graphs from a closed-family with forbidden minors $K_{3,3}, K_{5}$, graphs with bounded treewidth also are closed family graphs with no $H_{k}$ as minor. I assume that ...
69 views

### Strategies for preventing isolated nodes in a dynamically changing undirected cyclic graph

I'm building a mesh network where i need to detect the unexpected disappearance of a peer. Each node attempts to stay in communication with at least X peers. A node refuses connection from another ...
3k views

### Incremental Maximum Flow in Dynamic graphs

I'm looking for a fast algorithm to compute maximum flow in dynamic graphs. i.e given a graph $G=(V,E)$ and $s,t\in V$ we have maximum flow $F$ in $G$ from $s$ to the $t$. Then new/old node $u$ added/...
658 views

### Is there a example of Iterative Rounding in Approximation Algorithms for vertex weighted Graphs?

I am referring to the "Iterative Rounding" technique used by Kamal Jain for Steiner Network problem to obtain $2$ approximation factor algorithm. Is there any example where this technique is used for ...
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. ...
259 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 ...
711 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 ...
570 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 ...
290 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'...
145 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 ...
763 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 ...
327 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 ...
750 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. ...
727 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 ...
810 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 ...
552 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....
661 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 ...
730 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 ...
492 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 ...
813 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 ...
417 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 ...
383 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\...
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 ...