Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

25
votes
3answers
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 ...
4
votes
3answers
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 ...
1
vote
1answer
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 ...
7
votes
2answers
429 views

Dijkstra parallelization

I'd like to know what is the best method to parallelize the Dijkstra algorithm. Thanks.
5
votes
1answer
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 ...
2
votes
1answer
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 ...
12
votes
1answer
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 ...
5
votes
2answers
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 ...
9
votes
1answer
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 ...
12
votes
2answers
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 ...
9
votes
3answers
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? ...
1
vote
1answer
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 ...
3
votes
1answer
2k views

Tarjan Strongly Connected Components Question [closed]

Below is Tarjan's SCC algorithm as described in wikipedia. Input: Graph G = (V, E) ...
20
votes
5answers
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. ...
11
votes
2answers
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 ...
1
vote
0answers
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 ...
24
votes
2answers
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_%...
15
votes
1answer
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 ...
7
votes
0answers
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. ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
10
votes
1answer
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 ...
10
votes
1answer
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 ...
1
vote
0answers
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: ...
8
votes
1answer
471 views

Finding a maximum acyclic sub-tournament given two acyclic sub-tournaments

Given a tournament $T$ where $S_1$ and $S_2$ be two acyclic sub-tournament of $T$. Is the following problem NP-Complete: Finding a maximum acyclic sub-tournament $S$, which is subset of $S_1 \cup ...
18
votes
2answers
1k views

Maximum number of internally vertex-disjoint odd length s-t paths

Let $G$ be an undirected simple graph and let $s,t \in V(G)$ be distinct vertices. Let the length of a simple s-t path be the number of edges on the path. I am interested in computing the maximum size ...
8
votes
1answer
553 views

Max-clique in line graph of hypergraph

Suppose we have a multigraph (later, a multihypergraph). An edge-clique is a set of edges which all pairwise intersect (have at least one common vertex). Then any edge-clique $C$ in a multigraph ...
8
votes
1answer
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 ...
2
votes
2answers
2k views

Graph encoding algorithms that you know of ?

Is there any compilation of graph encoding algorithms? I know about Prufer and Huffman encoding. But papers say, prufer is not good enough to represent Minimum Spanning Trees in the sense it may ...
-1
votes
2answers
560 views

Minimum spanning tree algorithm. [closed]

Is the following a valid algorithm for finding a minimum spanning tree? Given a weighted graph with unique weights, remove the all edges that are the highest cost edge in any cycle of the original ...