Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
14
votes
1answer
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)$. ...
7
votes
2answers
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-...
8
votes
3answers
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 ...
8
votes
2answers
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 ...
1
vote
0answers
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 ...
12
votes
4answers
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/...
6
votes
1answer
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 ...
5
votes
3answers
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. ...
13
votes
1answer
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-...
10
votes
0answers
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 ...
6
votes
0answers
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 ...
10
votes
1answer
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 ...
7
votes
0answers
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 ...
1
vote
1answer
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)...
2
votes
2answers
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 ...
3
votes
0answers
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 ...
2
votes
1answer
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. ...
2
votes
1answer
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'...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
5
votes
1answer
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 ...
17
votes
1answer
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 ...
17
votes
1answer
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 ...
9
votes
2answers
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 ...
16
votes
2answers
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 ...
9
votes
2answers
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. ...
16
votes
1answer
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 ...
46
votes
4answers
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 ...
19
votes
2answers
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 ...
7
votes
2answers
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....
7
votes
2answers
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 ...
10
votes
1answer
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 ...
10
votes
1answer
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 ...
-6
votes
1answer
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?
8
votes
1answer
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. ...
11
votes
3answers
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 ...
3
votes
1answer
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 (...
19
votes
2answers
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 ...
7
votes
0answers
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 ...
5
votes
2answers
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 ...
12
votes
2answers
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 ...
5
votes
1answer
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 ...
7
votes
2answers
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 ...
21
votes
2answers
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. ...
10
votes
2answers
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. ...
1
vote
0answers
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 ...
10
votes
1answer
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:    &...
3
votes
0answers
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\...
1
vote
2answers
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 ...
20
votes
5answers
449 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 ...

1
14 15
16
17 18
20