A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

862 questions
Filter by
Sorted by
Tagged with
103 views

374 views

### Embedded dynamic programming (and planar subgraph isomorphism)

In Planar Subgraph Isomorphism Revisited, Frederic Dorn obtains an improved algorithm for Planar Subgraph Isomorphism, by using a technique he calls Embedded Dynamic Programming. This technique ...
327 views

2k views

### What's the approximation factor of this Max k-Cut approximation?

I'm thinking about an approximation algorithm for Max k-Cut. One simple and another one advance approximation algorithms are available here. The Max k-Cut problem is defined as follow: Assume we ...
322 views

### Find optimal room from which to visit all other rooms in a rectangular floorplan

Suppose we have an orthogonal polygon with holes (all walls are axis-parallel). All vertices can be on integer coordinates, if that helps. Partition the polygon into rectangular rooms. I would like ...
439 views

### MSOL optimization problems on graphs of bounded cliquewidth, with cardinality predicates

CMSOL is Counting Monadic Second Order Logic, i.e. a logic of graphs where the domain is the set of vertices and edges, there are predicates for vertex-vertex adjacency and edge-vertex incidence, ...
701 views

### Approximating transitive reduction of a transitive closure of a dag

Let's suppose a transitive closure $G^+$ of a dag $G$ is given and we want to compute an approximation of the transitive reduction $G^-$ such that the full transitive reduction is a subgraph of the ...
863 views

### Super Mario Flows in NP?

One classical extension of the max-flow problem is the "max-flow over time" problem: you are given a digraph, two nodes of which are distinguished as the source and the sink, where each arc has two ...
2k views

### Testing/Identifying a Topological Sorting

You're given a set of $n$ Directed Acyclic Graphs $G_1, G_2, ..., G_n$ over the same set of $m$ vertices $V$. You're also given a permutation of the set of vertices $(v_1,v_2,...,v_m)$. What is the ...
858 views

### Compact representation of DAG,

Given a DAG (which represents DDG – each node is a operation the in-edge/s show the operands from which inputs are taken) I want to obtain its compact representation of the graph, in such a way that: ...
232 views

### Searching for name of equivalence property in hamiltonian paths

This one has been bugging me for a while. A long time ago in undergrad, I noticed this while learning about TSP. Nobody recognized it and I basically gave up. Given a hamiltonian path, any subpath ...
3k views

### Number of reachable vertices in DAG for every vertex

Let $G(V,E)$ be an acyclic directed graph, such that out-degree of any vertex is $O(\log{|V|})$. For every vertex of $G$ we can count the number of reachable vertices, just by running dfs from every ...
115 views

### Is any related work to this m-trails problem ?

Yesterday, I discussed with one of my EE friends. She asked me an interesting problem and I simplify it by ignoring the bandwidth cost and model as following: Given a graph $G=(V,E)$ with its path set ...
2k views

### Finding twin vertices in graphs

Let $G=(V,E)$ be a graph. For a vertex $x\in V$, define $N(x)$ to be the (open) neighbourhood of $x$ in $G$. That is, $N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}$. Define two vertices $u,v$ in $G$ to be ...
1k views

### Finding minimum spanning 1-tree

We are considering a connected weighted graph G. 1-tree is a tree with one extra edge added (so it contains exactly one cycle). The task is to find minimum spanning 1-tree of G. I was thinking of ...
498 views

### Is there a polynomial-time algorithm to solve graph isomorphism for Delaunay graphs of (finite) hexagonal tessellations?

Given a finite plane, I have a hexagonal tessellation of that plane with a fixed-size regular hexagon. I then compute the Delaunay graph G for the tessellation. Given such a graph G, I delete specific ...
978 views

### Finding maximum weight arborescence in an edge-weighted DAG

Let $G$ be an edge-weighted DAG with a unique source $s$. The question is how to find out a maximum weight arborescence in $G$ rooted at $s$. When all edge weights are positive then the required ...
2k views

### Generalization of the Hungarian algorithm to general undirected graphs?

The Hungarian algorithm is a combinatorial optimization algorithm which solves the maximum weight bipartite matching problem in polynomial time and anticipated the later development of the important ...
312 views

### Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g.  Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
734 views

### How can I randomly generate bounded height spanning trees?

For a project that I am working on, I should generate random spanning trees with bounded height. Basically I do the following: 1) Generate a spanning tree 2) Check the feasibility, if feasible keep ...
743 views

### maintaining a balanced spanning tree of a growing undirected graph

I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph. I have an undirected graph that starts as a single node, the "root". At each ...
486 views

### Data set for Degree Constrained MST?

Degree Constrained Minimum Spanning Tree is an NP-hard problem. It differs from Minimum Spanning Tree in that, degree of every vertex should be $\leq$ some degree constrained. This is a well studied ...
943 views

### Finding a 5-cycle in a sparse graph efficiently.

(crossposted from MathOverflow) Hi, I was reading this thread: https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length I want to find a 5-cycle in a graph. Actually, what I really ...
965 views

### Reverse Graph Spectra Problem?

Usually one constructs a graph and then asks questions about the adjacency matrix's (or some close relative like the Laplacian) eigenvalue decomposition (also called the spectra of a graph). But what ...
472 views

### Is Degrees Of Separation NP Complete?

I'm doing a bit of research on doing social analysis between so called "hub" people. Basically what I want to try to do is determine the shortest paths between two individuals. The problem is that ...
2k views

### Algorithm for Longest Path in Undirected Weighted Graph [closed]

EDIT Dec 14th 2010 The algorithm is not correct: it's not the case that it always returns the optimal $W$. While reasoning on this and other similar questions, I've sketched an algorithm that, given ...
472 views

### Dijkstra parallelization

I'd like to know what is the best method to parallelize the Dijkstra algorithm. Thanks.
1k views

### Max Non-overlapping Path in Weighted Graph

I have a sparse weighted graph, and I want to find the longest path from a given vertex to any other vertex which does not go through the same vertex twice. You can think of it as, I am here, and I ...
229 views

### Weighted cycles in weighted line graphs

Assume a planar graph G, and all its vertices have degree at most 4. Consider a cycle in G. The weight of cycle c is the total weight of its vertices, and a vertex is weighted with the following ...
278 views

### Typical hardness of tree decomposition?

Tree decomposition is hard in the worst case but greedy method seems to be near-optimal on small real-life networks. Is anything known about hardness of tree decomposition of a "typical" instance of ...
791 views

### For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles

I have asked the question at Math SE and at SO, but I can't seem to get the answer I want. So I paraphrase the question and it here. In a planar graph $G$, one can easily find all the cycle basis by ...
348 views

### Is the backup problem NP-complete?

Is the following decision problem NP-complete: Let $G$ be an undirected graph and $b \le c$ two integers. Is it possible to select for every vertex of $G$ exactly $b$ different neighbors ...
2k views

### Number of mincuts of a graph without using Karger's algorithm

We know that Karger's mincut algorithm can be used to prove (in a non-constructive way) that the maximum number of possible mincuts a graph can have is $n \choose 2$. I was wondering if we could ...
856 views

### Tree decomposition for planar graphs

First asked on math.SE with no replies. Suppose I have a planar graph, with a planar embedding, how do I find tree decomposition? What is the optimal tree decomposition of a $d$-by-$d$ square grid? ...
1k views

### Kernighan–Lin algorithm and multiple gain functions

I want to know if there is an algorithm like KERNIGHAN-LIN for graph partitioning that can handle several (different) gain functions. Is there some technique to combine gain functions in one ...
2k views

### Tarjan Strongly Connected Components Question [closed]

Below is Tarjan's SCC algorithm as described in wikipedia. Input: Graph G = (V, E) ...
1k views

### Deterministic Parallel algorithm for perfect matching in general graphs?

In complexity class $\mathsf{P}$, there are some problems conjectured NOT to be in the class $\mathsf{NC}$, i.e. problems with deterministic parallel algorithms. Maximum Flow problem is one example. ...
230 views

### System of “stochastic equations”

Consider a graph with $n$ vertices and $m$ edges. The vertices are labelled with real variables $x_i$, where $x_1=0$ is fixed. Each edge represents a "measurement": for edge $(u,v)$, I obtain a ...
287 views

### Identifying sub graph in connected digraph [closed]

Hello I need some idea for a quick algorithm. Given a strongly connected undirected graph G with weighted edges, I would like to identify induced sub graph(it is required to be weakly connected) of ...
Suppose we want to find $$\sum_x \prod_{ij \in E} f(x_i,x_j)$$ or $$\max_x \prod_{ij \in E} f(x_i,x_j)$$ Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a ...