People who code: we want your input. Take the Survey

# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

944 questions
Filter by
Sorted by
Tagged with
1answer
526 views

### Given a graph, decide if its edge connectivity is at least n/2 or not

Chapter 1 of the book The Probabilistic Method, by Alon and Spencer mentions the following problem: Given a graph $G$, decide if its edge connectivity is at least $n/2$ or not. The author mentions ...
1answer
2k views

### Longest circuit in a directed graph

I have a very large directed graph (1M nodes) I am wondering what is the best algorithm for finding the longest (most number of nodes) cycle in the graph?
3answers
995 views

### Finding all cycles

I have a finite set $S$, a function $f:S\to S$, and a total order $<$ on $S$. I want to find the number of distinct cycles in $S$. For a given element $s\in S$ I can use Floyd's algorithm (or ...
2answers
365 views

### A variant of maximum matching: disjunctive constraints on the endpoints' degrees of edges in matching

The question is asked first at here. It described what the problem is and a trival greedy algorithm. Also the accepted answer gave a proof of its NP-completeness. Problem: Given a graph $G(V,E)$, ...
3answers
784 views

### The complexity of determining if a fixed graph is a minor of another

The result by Robertson and Seymour demonstrates an $O(n^3)$ algorithm for testing whether a fixed graph $G$ is a minor of $H$. I have two and a half questions on this topic: 1) It appears that there ...
0answers
494 views

### How to detect dead ends on a board / in a graph?

Given a (2D) board of quadratic cells (movement allowed between 4-neighbours), many of which are blocked, and given a certain starting position, how can I efficiently detect dead ends, i.e. regions of ...
1answer
246 views

### What is a totally ordered sort of sets of a partial order called?

Given a DAG, which can represent a partial order and has at least one topological sort. For example the graph >B / \ A >D \ / >C has two ...
0answers
580 views

### Complexity of finding the smallest well-covered completion

This is related to an earlier question on which graphs have the property that all maximal independent sets are maximum — such graphs turn out to be known as the well-covered graphs. Any graph $G$ is ...
3answers
3k views

### Approximation algorithms for dominating set problem

I am working on approximation algorithms for minimum dominating set problem. In particular, I am interested in graphs classes restricted by forbidden induced subgraphs. Since the domination problem ...
0answers
355 views

### Connected Components over Graph with “colored” edges.

We have an undirected graph $G(V,E)$. Each edge $e \in E$ is associated with a set $C_{e}\neq \emptyset$ of colors, $C_{e} \subseteq C$. The problem is to find all the colored connected components. ...
1answer
2k views

### Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed

Update: This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution. http://www.youtube.com/watch?v=VbSwwos4R2E I ...
1answer
180 views

### Decomposing complete graphs into clique-free graphs of certain size

Modified in accordance with Tsuyoshi's comment which seems to generalize. Let $K_{m}$ be a complete graph on $m$ vertices. Is there a way to partition the graphs in to sets of graphs that have no ...
3answers
291 views

### Best algorithm for calculating lists of neighbours

Given a collection of thousands of points in 3D, I need to get the list of neighbours for each particle that fall inside some cutoff value (in terms of euclidean distance), and if possible, sorted ...
0answers
545 views

### Difference between Primal Dual Algorithm for Proper and Uncrossable Functions

Williamson with many of his co-authors had worked on generalized primal dual algorithms on edge weighted graphs considering three types of functions: (1) super-modular functions (2) proper functions ...
2answers
178 views

### Predict user's future location - location awareness mobile computing

This question is a part of an online course (Mobility Data Management) that I am currently auditing. A part of the project is to implement a system that can predict user's future location. This kind ...
1answer
312 views

### Shortest path in a DAG consisting of multiple copies of a smaller DAG

Let's say we have $k$ weighted DAGs (directed acyclic graphs) $$H_1 = (V_1, A_1), \dots, H_k = (V_k, A_k)$$ that are copies of one another. Now consider another weighted DAG $G$ that is built by ...
3answers
605 views

### Implemented code to compute pathwidth (= Node search number, vertex separation number, interval thickness)

I am looking for an implementation of an algorithm to compute the pathwidth of a graph. It is well known that computing the pathwidth is equivalent to computing the node searching number, vertex ...
1answer
2k views

### Longest path in Complete Directed Graphs

I searched in Google and checked similar questions on this site, but couldn't find an answer for my problem. I hope this place is appropriate for my problem. The problem is formulated as follows: We ...
0answers
425 views

### Predecessor matrix storing

What is the time complexity of computing betweenness centrality if we are given the shortest path predecessor matrix of a graph? Predecessor matrix cells look like this: If node $i$ and node $j$ are ...
0answers
273 views

### How to quantify the tree-like-ness of a graph?

What are good measures of tree-like-ness of a graph and algorithms for calculating them?
0answers
269 views

### Algorithm for choosing unique items from a collection of sets of items

I have a number of sets, each containing items with a numerical value and a string. I want to choose one item out of each set, so that: 1. the strings of the chosen items form a set (i.e. the strings ...
2answers
422 views

### Efficient algorithms for searching a collection of trees

I have a large dataset of trees and I would like to search it by specifying a treelet (connected subgraph). The query should return all the occourrences of the treelet in the dataset. Are there ...
2answers
4k views

### Reducing redundant edges from a dependency graph

I have a DAG of dependencies that contains lots of redundant edges (see example below). I want a "quick" algorithm (ie. can handle a graph with several thousands of nodes/edges) that finds a minimal ...
3answers
6k views

### shortest path & max flow

I am trying to improve my algorithmic knowledge during the summer break and i found this problem in a book. We have an undirected graph $G=(V,E$) with starting node $s\in V$ and last node $t \in V$ ...
2answers
525 views

### Shortest Path Algorithm for large graph but short paths

I have a graph (say, about a million vertices) where the degree of every vertex is somewhat large (about 100 000). We want to find the shortest path between two vertices -- but we know the graph is ...
1answer
309 views

### Parallel algorithms to color interval graphs

Several NP-hard graph problems get easy if we consider interval graphs. There is a greedy algorithm to color optimally an interval graph. Just sort the intervals according their left endpoints and ...
1answer
238 views

### Connectivity Problem

Hi. I have a problem but not sure if there is some literature on it or whether it has a standard name. Please let me know some reference from where I can begin. Given undirected graph along with some ...
1answer
278 views

### 3 colorable graphs

I was trying to understand the underlying difficulty of coloring 3 colorable graphs with as least number of colors as possible. Though i am aware of hardness result of coloring it with 4 colors, i ...
2answers
1k views

### Shortest paths disallowing each edge

I'd appreciate any pointers or terms that could get me started in the right direction. We have a directed graph $G=(V,E)$ and lengths $l_{ij}$ for each edge $ij$ that can be assumed positive. There ...
3answers
3k views

### Exact algorithm for edge coloring

Wikipedia lists several exact algorithms for graph vertex coloring. Are there any exact algorithms that are designed specifically for graph edge coloring? edit: Just came across my mind, i think it ...
3answers
641 views

### Enumerating all pairs of disjoint paths

Given a directed graph $G = (V,E)$ and two vertices $s,t \in V$. A pair of simple paths $p_1,p_2$ from $s$ to $t$ is edge disjoint if they don't share an edge. Using max flow, it is easy to decide ...
1answer
329 views

### Graph representation using edge sets

Given a directed graph $(V,E)$ with $E\subseteq V\times V$, a source vertex $v_0\in V$ from which all other vertices are reachable, and a set $I$ of unique identifiers for the edges in $E$ (i.e., ...
2answers
503 views

### Lattice problems

There has been a fair amount of work on computational problems for partial orders (e.g., recognition, jump number, comparability graph recognition, etc...). I am curious what work specific to ...
5answers
11k views

### Vertex Cover applications in the real world

What applications does the Vertex Cover Problem have in the real world? Which industry or research projects use actually implemented software that is based on theoretical results for the Vertex Cover ...
3answers
458 views

### Graphs to download

Possible Duplicate: Data for testing graph algorithms I recently developed a parallel algorithm to solve the vertex cover problem. now i need some graphs so i can test the speed of my algorithm ...
4answers
13k views

### What is the computational complexity of “solving” chess?

The basic idea of backwards induction is to start with all the possible final positions of a game in which player X wins. So for chess, look at all the ways White can checkmate Black. Now work ...
3answers
373 views

### Heuristics for graph bisection

i'm trying to find an algorithm that will divide my graph in 2 parts by telling me what connections should be broken but the 2 parts should contain about the same number of nodes its for a practical ...
1answer
544 views

### Approximation for counting the number of simple $s$-$t$ paths in a general graph

I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does ...
2answers
548 views

### Does there exist a data structure for quick list manipulation and order queries?

We have a set, $L$, of lists of elements from the set $N = \{ 1, 2, 3, ..., n \}$. Each element from $N$ appears in a single list in $L$. I am looking for a data structure which can perform the ...
4answers
3k views

### Finding cliques in a big graph

I would like to find (all) cliques in a given graph with 8,568 vertices and 12,726,708 edges. The vertex with the lowes degree has 2000, the vertext with the highest degree has 4007. The cliques ...
1answer
167 views

### Using MSOL for solving BIDS problem

From "Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width" (B. Courcelle et al) we know that any problem that can be written on MSOL (Monadic Second Order Logic) has a linear ...
1answer
513 views

### Does this graph problem have a formal name?

Given an undirected weighted graph where an edge exists between every pair of nodes (n1,n2) with cost C(n1,n2), find the shortest path (possibly revisiting nodes, possibly revisiting edges) through ...
0answers
261 views

### Integral k-multicommodity flow with demands on acyclic digraphs wirh maximum outdegree two

It is well-known that different variants of Multicommodity flow problem are NP-complete. What is the complexity of the following variant, that is, the integral k-multicommodity flow problem with ...
3answers
1k views

### Regular Graphs and Isomorphism

I would like to ask whether there is an already published result on that: We take all possible different paths between each pair of nodes of two connected regular (with degree $d$ let's say, and ...
1answer
817 views

### Modular Decomposition and Clique-width

I am trying to understand some concepts about Modular decomposition and Clique-width graphs. In this paper ("On P4-tidy graphs"), there is a proof of how to solve optimization problems like clique-...
1answer
247 views

### How to determine if a labelled digraph contains a cycle with given labels?

Suppose $G = (V, E)$ is a digraph of bounded degree. Suppose each edge in $E$ is labelled with a number from the set $X = \{1, ..., n\}$ and for each vertex $v \in V$ and each $x \in X$ there is at ...
1answer
338 views

### Are there good implementations for easy subclasses of NP-hard graph problems

Given graph G = (V,E) I need to solve some problems that are NP-Complete on G. However it could be that G belongs to some class where these problems has polynomial solutions (here is a great resource ...
1answer
260 views

### Explain 0-extension algorithm

I'm trying to implement an approximation algorithm for the 0-extension problem I found the following paper: Approximation Algorithms for the 0-extension problem by Gruia Calinescu, Howard ...
1answer
223 views

### Weighted Metric Graph: ratio of sum of wts of edges to the wt of MST

I am working on complete metric graph (V,d) where shortest distance is used as metric. The question is how large can be the ratio of the sum of weights of all edges to the weight of the MST (minimum ...
1answer
747 views

### Largest common subgraph of two maximal planar graphs

Consider the following problem - Given maximal planar graphs $G_1$ and $G_2$, find the graph $G$ with maximum number of edges such that there is a subgraph (not necessarily induced) in both $G_1$ and ...