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

Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

Filter by
Sorted by
Tagged with
13
votes
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 ...
2
votes
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?
9
votes
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 ...
5
votes
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)$, ...
26
votes
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 ...
0
votes
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 ...
2
votes
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 ...
20
votes
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 ...
9
votes
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 ...
3
votes
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. ...
6
votes
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 ...
2
votes
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 ...
6
votes
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 ...
7
votes
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 ...
2
votes
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 ...
3
votes
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 ...
13
votes
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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?
2
votes
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 ...
9
votes
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 ...
8
votes
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 ...
1
vote
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$ ...
4
votes
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 ...
7
votes
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 ...
2
votes
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 ...
4
votes
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 ...
9
votes
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 ...
4
votes
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 ...
10
votes
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 ...
5
votes
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., ...
10
votes
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 ...
24
votes
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 ...
2
votes
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 ...
9
votes
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 ...
2
votes
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 ...
17
votes
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 ...
9
votes
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 ...
3
votes
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 ...
7
votes
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 ...
4
votes
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 ...
4
votes
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 ...
11
votes
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 ...
15
votes
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-...
4
votes
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 ...
3
votes
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 ...
2
votes
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 ...
1
vote
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 ...
13
votes
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 ...