# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

830 questions
922 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 ...
470 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 ...
429 views

### Dijkstra parallelization

I'd like to know what is the best method to parallelize the Dijkstra algorithm. Thanks.
947 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 ...
222 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 ...
274 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 ...
724 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 ...
347 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 ...
815 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 ...
1k views

### What is the best exact algorithm to compute the core of a graph?

A graph H is a core if any homomorphism from H to itself is a bijection. A subgraph H of G is a core of G if H is a core and there is a homomorphism from G to H. http://en.wikipedia.org/wiki/Core_%...
418 views

### Graph decompositions for combining “local” functions of vertex labelings

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 ...
164 views

### Finding the set of paths of smallest cumulated length that cover a given set of patterns

First of all, sorry for this long and maybe not very informative title... Context: Let $G=(V,E)$ be a directed graph, let $v_0 \in V$ be the initial node of paths that I will consider in the graph. ...
440 views

### Finding islands of vertices in a network of roads containing one-way streets [closed]

I am working on GIS project where we are making use of road maps that may contain one-way streets. We are writing some debugging tools one of which I want to design to find "Islands". This would ...
656 views

### Heuristics for the minimum-weight $k$-clique problem

Hello Does someone have an idea for heuristics for the problem: Given undirected weighted(weights on edges) complete graph $G(V,E)[|V|=n,|E| = m]$, find a clique of size $k < n$(k is number of ...
1k views

### Pruning a strongly connected digraph

Given a strongly connected digraph G with weighted edges, I would like to identify edges that are provably not part of any minimal strongly connected subgraph (MSCS) of G. One method for finding such ...
790 views

### Finding short and fat paths

Motivation: In standard augmenting path maxflow algorithms, the inner loop requires finding paths from source to sink in a directed, weighted graph. Theoretically, it is well-known that in order for ...
2k views

### DAG partitioning to subgraphs

Given a DAG with $|V| = n$ and has $s$ sources, we have to present subgraphs such that each subgraph has approximately $k_1=\sqrt{s}$ sources and approximately $k_2=\sqrt{n}$ nodes. (Note: ...
471 views

485 views

### Algorithms and computational complexity of clique and biclique covers

I've been reading a paper by a mathematical chemist. He proposes some indices to measure the complexity of molecules. From here on in, instead of molecules, think undirected connected graphs: a ...