Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
9
votes
3answers
811 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 ...
20
votes
2answers
833 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 ...
2
votes
0answers
503 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 ...
21
votes
2answers
1k 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 ...
25
votes
3answers
999 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
499 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 ...
8
votes
2answers
478 views

Dijkstra parallelization

I'd like to know what is the best method to parallelize the Dijkstra algorithm. Thanks.
5
votes
1answer
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 ...
2
votes
1answer
234 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
303 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
818 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
369 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 ...
15
votes
2answers
3k 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
927 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
2k 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
252 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
289 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
448 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
165 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
443 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
725 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
945 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: ...
9
votes
1answer
529 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
707 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
503 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
593 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 ...

1
15 16 17 18
19