# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

944 questions
Filter by
Sorted by
Tagged with
2answers
373 views

### Subset Numbering

Fix $k\ge5$. For any big enough $n$, we would like to label all subsets of $\{1..n\}$ of size exactly $n/k$ by positive integers from $\{1...T\}$. We would like this labelling to satisfy the following ...
0answers
75 views

### Load-balancing; Alternate methods of keeping track of nodes?

Reading various articles in the literature have given me only a few decent methods of keeping track of nodes before->after load-balancing them on a very large network. One popular method uses virtual-...
1answer
319 views

### Decomposition by Clique Separators

Tarjan described a procedure for decomposing a graph using clique separators in "Decomposition by clique separators", RE Tarjan - Discrete mathematics, 1985 - Elsevier. He also proposed different ...
1answer
402 views

### Is there a suitable algorithm to draw a mixed constituency/dependency graph in a coordinate system?

I am looking for an algorithm to draw a mixed constituency/dependency graph (for a linguistic application). Such a graph would have two different types of vertices (tokens, nodes), and two different ...
1answer
368 views

### Lower Bounds on Running time of Graph Algorithms

Are there any non-trivial lower bounds on the running time of graph algorithms in RAM/PRAM/ models of computation ? I am not looking for the NP-Hardness results here. Following is a result that I ...
1answer
144 views

### c factor in PageRank

In page 3 of PageRank paper is mentioned: let c be a factor used for normalization (so that the total rank of all web pages is constant). What is the use of c...
2answers
371 views

### What is the complexity of chordalization?

A graph $G=(V,E)$ is a chordal graph, if it does not contain an induced cycle of length at least four. We say a graph $H$ is a chordalization of graph $G$, if $H$ contains $G$ as a subgraph, and $H$ ...
0answers
156 views

### Partitioning the vertices of a complete graph with weights on both vertices and edges with constraints

Given the complete graph on n vertices. Each vertex and each edge has a positive weight associated with it. What is desired is to partition the vertices into parts so that the sum of the weights of ...
0answers
611 views

### K-shortest path in large sparse graph

I am an engineer and looking for a reference to find k-shortest path's in a large sparse graph. In the search for it, I came acorss Yen's ranking loopless algorithm and an improved implementation of ...
0answers
113 views

### Can one find good distance-2-separators in planar graphs?

It is known that planar graphs admit "good" separators, allowing to design PTASes for specific problems such as MINIMUM INDEPENDENT SET by recursive separation of the graph. However, it seems that ...
1answer
1k views

### Generating a tower defense maze, aka Finding the K most vital nodes (“nodewise interdiction”) in an unweighted grid-graph

In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls. Enemies take the shortest path from start to finish without passing through any walls (they aren't usually ...
2answers
332 views

### Algorithms for creating a directed network with a given 3-node motifs distribution

I am looking for algorithms to create directed networks with an arbitrary distribution of 3-node network motifs (i.e. subgraphs of the order 3), see this picture from O. Sporns, R. Kotter, Motifs in ...
1answer
258 views

1answer
2k views

### Finding the nearest node to a given set of nodes in a graph

I am looking for an algorithm that, given a large weighted undirected graph, would find the node that has minimum average distance from a given set of nodes in the graph.
1answer
2k views

1answer
990 views

### Polynomial time algorithm to solve the TSP on an m by n solid grid

Is there a polynomial algorithm to solve TSP (or Ham Cycle) on an m by n solid grid graph whose points are at unit distance apart? I've heard about Umans and Lenhart research paper but reading such ...
3answers
522 views

### Complexity of “is a graph a product”

This question arises out of pure curiosity (it came up while thinking about unshuffling a string, but I'm not sure if it's actually related) so I hope it's appropriate. There are various graph ...
4answers
2k views

### Is the feedback vertex set problem on planar bounded degree graphs hard?

Is it known whether the feedback vertex set problem on undirected planar graphs of bounded degree is $\mathsf{NP}$-hard?
0answers
93 views

### Belief Propagation on MRF with complex cliques

Is there a belief propagation algorithm for exact inference on a MRF with complex clique structures (i.e. ones involving more than 2 neighbours)? For MRF's with cliques that only involve pairwise ...
1answer
371 views

### Complexity of the directed Steiner tree problem on special graph classes

I am interested in the complexity of the directed Steiner tree problem: Given a weighted digraph $D=(V,E)$, a root $r\in V$ of $D$, and a set of terminals $T\subseteq V$. The objective is to find a ...
1answer
947 views

### Graph layout algorithm

I have an undirected graph on matris by vertex adjacency relations like that; ...
2answers
479 views

### Reconstructing a tree from separator queries

Suppose $T$ is an constant-degree tree whose structure we do not know. The problem is to output the tree $T$ by asking queries of the form: "Does the node $x$ lie on the path from node $a$ to node $b$?...
0answers
1k views

### Sparse graphs versus dense graphs

I am curious if there are graphs problems for which either - we know that time and/or space complexity is independent of graph sparsity we do not know whether or not graph sparsity can be exploited ...
2answers
491 views