Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
10
votes
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 ...
3
votes
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-...
6
votes
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 ...
9
votes
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 ...
8
votes
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 ...
2
votes
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...
5
votes
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$ ...
3
votes
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 ...
3
votes
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 ...
7
votes
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 ...
22
votes
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 ...
3
votes
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 ...
3
votes
1answer
258 views

Minimum length walk from s to t covering a subset of vertices

I want to find the current literature for the following problem (I have searched on google/asked friends/some Profs didn't get much useful results yet): Input: weighted undirected graph G = (V,E), $...
6
votes
1answer
408 views

In a random perfect matching of a regular bipartite graph, are all edges equally probable?

Consider a d-regular bipartite graph G, for d>=1. Obviously, G contains a perfect matching. Consider a perfect matching M in G chosen uniformly at random from all perfect matchings in G. Is it the ...
2
votes
0answers
112 views

Target-Value Search [closed]

Given an edge-weighted graph $G=(V,E)$ the problem of finding the shortest path is known to be in P ---and indeed a simple approach would be Dijkstra's algorithm which can solve this problem in $O(V^2)...
2
votes
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.
0
votes
1answer
2k views

Linear Programming with Modulo Linear Constraints

Given $G = (V,E)$ I can formulate a relaxation of graph $K$-coloring as: find feasible point s.t. $\min \sum_{ij}v_{ij}$ for all $(i,j)$ in $E$ $z_{ij} \le (c_i - c_j) \bmod k$ (i) $z_{ij} \le (...
2
votes
1answer
320 views

Do you know a shortest path algorithm for weighted graphs with hard time windows on the edges and waiting allowed?

Title says it all. I have a weighted Graph G={V,E,ETW} where V is the node set, E the edge set and ETW is a set of edge time windows. A edge time window is a 3-Tuple (edge, starttime, endtime) with ...
2
votes
1answer
546 views

techniques or examples of analyzing a series of graphs

Let there be a sequence of graphs $G_1, G_2, G_3, ...$ constructed using some particular approach or algorithm. in this particular case $G_n$ is constructed by modifying $G_{n-1}$ in some "...
26
votes
4answers
737 views

How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph?

I am not a computer science theorist, but think this real world problem belongs here. The problem My company have several units accross the country. We offered to employees the possibility to work ...
8
votes
1answer
181 views

Graph partitioning, balancing on within subset edge weights

I'm interested in pointers to algorithms (approximation algorithms are fine) that attempt to partition a graph into two subsets such that the sum of the edge weights within each subset is (...
18
votes
4answers
879 views

Parametrized Algorithm for Finding Bicliques

Given an $n$ vertex undirected graph, what is the best known runtime bound for finding a subgraph which is a $k\times k$-biclique? Are there faster parametrized algorithms than the $\binom{n}{k}\mbox{...
-5
votes
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 ...
25
votes
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 ...
13
votes
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?
1
vote
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 ...
6
votes
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 ...
1
vote
1answer
947 views

Graph layout algorithm

I have an undirected graph on matris by vertex adjacency relations like that; ...
18
votes
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$?...
7
votes
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 ...
2
votes
2answers
491 views

Is the following optimization problem NP-hard?

Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$, is given. E.g. $S=\{(1,3), (2,3), (1,4), (2,4), (3,1), (3,4)\}$ . For each element $(i,j)$, we have weight $w_{...
6
votes
1answer
244 views

Self-referentially defined graph structures

It is possible to define graphs $G$ such that whether an edge exists between two vertices $v_1$ and $v_2$ depends on non-local properties of $G$. In particular, I am interested in directed graphs ...
5
votes
0answers
208 views

Minimum infeasible subgraph in assignment problem

Given a bipartite graph $G$ with node set $(X+Y)$. Each node $x \in X$ has to be assigned to 1 node $y \in Y$. Assignment is only possible if there is an edge between $x \in X$ and $y\in Y$. ...
16
votes
2answers
537 views

Representing non-planar graphs with overlapping circles

We know that we can represent any planar graph by a set of circles in the plane, known as a coin graph. Each circle represents a vertex and there is an edge between two vertices if and only if the ...
9
votes
2answers
328 views

Complexity of finding a graph separator with a given property

Are there any known results on the complexity of finding a separator (of any size) satisfying a given property? I know that a clique separator is easy (polynomial time) to find and also know that ...
8
votes
0answers
191 views

what is the best heuristic to solve 3AP with Euclidean costs?

As is well known, assignment problems for $n$-partite graphs, with $n$>2 are NP-hard, where as assignment problems on bipartite graphs can be solved in polynomial time using the Kuhn's Hungarian ...
16
votes
6answers
2k views

When are two algorithms said to be “similar”?

I do not work in theory, but my work requires reading (and understanding) theory papers every once in a while. Once I understand a (set of) results, I discuss these results with people I work with, ...
3
votes
2answers
625 views

Maximum fractional packing of spanning trees.

Given a graph $G$, let $\{T_1,\ldots,T_k\}$ be a set of spanning trees with associated nonnegative weights $\{w_1,\ldots,w_k\}$ such that for every edge $e$, $\sum_{e\in T_i}w_i \leq 1$. This is a ...
0
votes
0answers
527 views

suffix tree: about Ukkonen's algorithm

I have specific question about suffix trees. I am reading the book Algorithms on strings_trees and sequence. I cannot understand details of Ukkonen's algorithm for constructing suffix trees. Why ...
9
votes
4answers
486 views

Treewidth and Packing

My question is a bit vague. I have been wondering if (and how), we can apply the notion of treewidth to packing problems in graphs. I would be happy with any insights or references of past research ...
11
votes
0answers
239 views

Inapproximability of multiterminal cut

In the multiterminal cut the input is a graph $G$ and a subset $T$ of its vertices. The task is to remove the minimum number of edges from $G$ such that there is no path connecting any distinct ...
14
votes
3answers
521 views

Is this optimum travelling problem under deadlines NP-hard on trees?

One of my friends asks me the following scheduling problem on tree. I find it is very clean and interesting. Is there any reference for it? Problem: There is a tree $T(V,E)$, each edge has symmetric ...
7
votes
3answers
514 views

Algebraic formulation for packing problem

My question is regarding the algebraic formulation for packing problems in graphs. Taking an example, suppose I am interested in the problem of finding if there is a packing of k edge disjoint ...
14
votes
1answer
591 views

Exact Algorithm for edge labeling problem in DAG

I am implementing some system part of which requires some help. I am therefore framing it as a graph problem to make it domain independent. Problem: We are given directed acyclic graph $G=(V,E)$. ...
7
votes
2answers
1k views

Edge-weight updates in all pair shortest path problem

I want to calculate all-pairs shortest paths on a graph with roughly 50,000 nodes representing a city-wide road network. An answer to my previous question led me to Hiroki Yanagisawa's paper "A multi-...
8
votes
3answers
2k views

Finding triangles in a graph: other approaches besides property testing?

We're working on a paper that presents some algorithms for finding triangles and network motifs (constant size subgraphs, also known as graphlets) in a distributed setting. We characterize the ...
8
votes
2answers
341 views

Max-Cut Of Minor Closed Family

It's well known that planar graphs from a closed-family with forbidden minors $K_{3,3}, K_{5}$, graphs with bounded treewidth also are closed family graphs with no $H_{k}$ as minor. I assume that ...
1
vote
0answers
69 views

Strategies for preventing isolated nodes in a dynamically changing undirected cyclic graph

I'm building a mesh network where i need to detect the unexpected disappearance of a peer. Each node attempts to stay in communication with at least X peers. A node refuses connection from another ...
12
votes
4answers
3k views

Incremental Maximum Flow in Dynamic graphs

I'm looking for a fast algorithm to compute maximum flow in dynamic graphs. i.e given a graph $G=(V,E)$ and $s,t\in V$ we have maximum flow $F$ in $G$ from $s$ to the $t$. Then new/old node $u$ added/...
6
votes
1answer
657 views

Is there a example of Iterative Rounding in Approximation Algorithms for vertex weighted Graphs?

I am referring to the "Iterative Rounding" technique used by Kamal Jain for Steiner Network problem to obtain $2$ approximation factor algorithm. Is there any example where this technique is used for ...

1
13 14
15
16 17
19