Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

learn more… | top users | synonyms (1)

1
vote
1answer
43 views

Non-Approximate Dynamic All-Pairs Shortest Path algorithm for Undirected, Unweighted Graphs?

I am looking for an algorithm involving adding unweighted edges to an empty, undirected graph (with vertices) and then for each, updating the table of shortest paths. An example is if we have ...
1
vote
1answer
38 views
2
votes
2answers
90 views

Finding a node that is minimal w.r.t. maximum distance to any other node [on hold]

Given a graph and an edge in the graph, I want to find a point on this edge that makes the maximum distance from all the nodes to this point minimized. Is there any graph-theory based algorithm that ...
3
votes
1answer
58 views

Finding independent sets so that all nodes are hit frequently

I have a problem, and I appreciate it if you could share your thoughts. Assume that I have a graph. Assume that I have $k$ iterations. I want to find only one independent set (IS) in the graph in ...
0
votes
1answer
50 views

Use Dijkstra to find negative cycles in a graph [closed]

I will state the problem: Suggest an algorithm that works in $O(|E| + |V|log|V|)$ time that checks if there are negative cycles in a graph. So, I saw the runtime, and I immediately said we need ...
2
votes
1answer
44 views

Finding Kernel in DAG

Let $G=(V,E)$ be a DAG. A subset $A \subseteq V$ is called a kernel if for all $u,v \in A$ $uv \notin E$ and for all $v \in V-A$ there exists an $a \in A$ such that $av \in E$ (note again, this is a ...
3
votes
3answers
125 views

Efficient algorithm to find subgraph

I have a really nasty problem (for me) at hand and I was wishing some of you may know an efficient algorithm to solve it. Thanks to all of you in advance. My problem I have a set of elements (that ...
2
votes
1answer
65 views

Doubt regarding Maximum Bipartite Matching

I was given this question by a friend: "You are given 3 sets of size n, X,Y and Z. Devise an algorithm to find maximum number of different pairings (u,v,w,x) such that u,v,w,x belong to X,Y,Z and X ...
5
votes
1answer
99 views

Transition coverage for a DFA

Let $G$ be a directed graph, with a single source node $s$. I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where ...
2
votes
0answers
21 views

How can I find data to compare with my work's results? [duplicate]

My Masters thesis is on task graph scheduling for multi core processors. I have developed a new task clustering and scheduling algorithm. I wanted to know about how can I find data to compare it with ...
1
vote
0answers
31 views

Shortest path with min-sum multiplication and Boltzmann distribution

My professor presented a method to find shortest paths using the min-sum multiplication and Boltzmann distribution. He multiplies the adjacency matrix many times and takes the $\beta$ of Boltzmann ...
1
vote
2answers
115 views

Finding shortest path from a node to any node of a particular type [closed]

I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is ...
-1
votes
0answers
16 views

Max K-Cut Randomized Algorithm

The simplest heuristic for MAX k-CUT is just to randomly partition V into k sets. If Pb denotes the (random) partition produced and P∗ denotes the optimum partition then it is easy to see that ...
0
votes
2answers
63 views

Maximum length path between any two nodes in a tree with possible negative edge weights

Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a ...
-1
votes
1answer
32 views

Is finding negative cycle vertices NP complete?

I was trying to find all the negative cycle vertices using the Bellman–Ford algorithm using this paper solution 7.1(b) in $O(V)$ by tracing back the predecessor subgraph.It is also stated in ...
4
votes
1answer
115 views

How to reduce the cost of search based on previous BFS?

I got an unweighted, undirected graph, with $N$ vertices, where each vertex has degree $K$. In my case its a grid with dynamic obstacles. My goal is to output a map, based on given location on the ...
1
vote
1answer
185 views

Checking whether two paths are intersecting in a tree

The problem I have is given a Tree graph , and two paths from u1 to v1 and u2 to v2 where u1,u2,v1,v2 are vertices of the Tree . How efficiently can we check that whether they are vertex disjoint ...
1
vote
1answer
45 views

Bellman-Ford without getting stopped by negative cycles

Let $s$ be the source vertex. In the standard Bellman-Ford algorithm (e.g. the version found in CLRS), when there is a negative cycle reachable form $s$, the algorithm will return that a negative ...
0
votes
1answer
59 views

Floyd–Warshall algorithm on undirected graph

I am referring to the algorithm from the Wikipedia page on the Floyd–Warshall algorithm. In case of undirected graphs should I change the assignment statement inside the ...
2
votes
1answer
21 views

Conditional RB Tree union

Input: 2 RB Trees A B, so that both values in a certain range, so that B's range is smaller than A in both sides. Ex. B's range can be [100...200] and A's range is [0...1000] Output: Unite A and B to ...
1
vote
1answer
32 views

Order of steps in Kosaraju-Sharir

The Wikipedia summary of the Kosaraju-Sharir algorithm is as follows: Let G be a directed graph and S be an empty stack. While S does not contain all vertices. Choose an arbitrary ...
1
vote
2answers
68 views

directed graph data structure with fast in/out neighbor query

If I store a directed graph $G$ in adjacency list format, one can find all the out-neighbors $j$ of a given vertex $i$ in $\mathcal O(d)$ time, where $d$ is the max degree of the graph. These are all ...
2
votes
2answers
43 views

Create a random graph based on the Degree Distribution and Clustering Coefficient Distribution

I am currently working with a very large Social Network and I want to recreate this graph with a smaller dimension, using the original Degree Distribution and Clustering Coefficient Distribution. The ...
1
vote
1answer
105 views

Is there a problem that cannot be represented using graph?

It is obvious that the representational power of graphs are huge. Is there a problem that cannot be represented using graph? I have recently asked this question to my students and no answers came up. ...
3
votes
1answer
96 views

Shortest even path that goes through a vertex

Given an undirected and connected graph $G=(V,E)$ and two vertices $s,t$ and a vertex $d \in V- \{s,t\}$, we would like to define a legal path as a path from $s$ to $t$, passes through $d$ (at least ...
1
vote
1answer
36 views

How to modify Bellman-Ford algorithm for this specific Minimum Cost Flow problem?

I'm trying to design an algorithm for the following optimization problem. Suppose that $G=(V, E)$ is a digraph where $V$ and $E$ are sets of vertices and edges of $G$, respectively. $|V| = n$ and $|E| ...
2
votes
2answers
182 views

The Gas Station Problem - fast implementation

Recently I was asking about the algorithm to solve The Gas Station Problem and I got useful answer. Unfortunately solution with transforming a graph to complete graph and then preparing another one to ...
8
votes
3answers
701 views

Understanding an algorithm for the gas station problem

In the gas station problem we are given $n$ cities $\{ 0, \ldots, n-1 \}$ and roads between them. Each road has length and each city defines price of the fuel. One unit of road costs one unit of fuel. ...
7
votes
1answer
112 views

Research in Graph Theory versus Graph Algorithms

I have a very generic question to ask. It is related to research. I'm interested in Graph theory. I have done a course in it. I have done some topics related to both graph theory as a point of ...
0
votes
2answers
41 views

Given a graph, finding if a node has three adjacents from a node subset $N$

Given a graph $G = (V,E)$, assume that we have two disjoint vertex sets $N = \{n_1, n_2 ...\} \subset V$ and $P = \{p_1, p_2, ...\} \subset V$ such that $N \bigcup P \neq V$. I want to find if there ...
2
votes
1answer
43 views

Choose $n/2$ vertices and guarantee $3/4$ of edges are accounted for proof

Give a polynomial-time algorithm that finds ceil(V/2) vertices that collectively account for at least three-fourths (3/4) of the edges in an arbitrary undirected graph. The algorithm I have come up ...
5
votes
2answers
693 views

Can we represent all computer programs as graphs?

I was thinking the other day, and it occurred to me that computer programs all seem to be representable as a graph (an abstract syntax tree for example), or, once common expressions are combined, an ...
4
votes
1answer
67 views

How to perform local search on simple paths?

I have a local search problem. The set of valid solutions are all the simple paths (i.e. without repeated nodes) from a node $S$ to a node $T$ in a directed graph. The question is: given a current ...
-2
votes
1answer
65 views

MIS algorithm for Tree in O(log* n) time

I know Distributed Graph Coloring algorithm in O(log* n) which is given at P11: Vertex Coloring Same for Maximal Independent Set [MIS] they gave remark like algorithms exist in O(log* n) time at P70: ...
1
vote
3answers
88 views

Can not follow the example for max-flow-min-cut on Wikipedia

This Wikipedia example is very confusing. Its saying the max flow = min cut. But I see the max flow = 9 and the min cut = 7. If not, how does the capacity =min cut here? Which is the max flow min cut ...
0
votes
1answer
28 views

shortest time based on traffic congestion data [closed]

I want to develop one algorithm which can predict shortest time to be taken to go to a destination from a source in a road network based on traffic congestion data. Consider that I have a server ...
2
votes
1answer
37 views

Is traversing an unconnected graph possible?

I have been assigned a fun project: design and implement a program that maintains the data of a simple social network. Each person in the network should have a profile that contains his name, current ...
2
votes
0answers
47 views

Enumerating all paths through directed graph with loops and splits

I am looking for a way to enumerate all the possible paths between a source and one or more sinks in a directed graph, with loops. Also, some edges must enforce a maximum number of traversals (n), so ...
2
votes
1answer
38 views

Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost

Given a fully connected graph $G$, suppose that we are searching for a simple path $P$ with a specific cost $c$. Is answering to that problem yes or no equivalent to subset-sum problem? What would ...
0
votes
1answer
96 views

Reducing from 3-COLOR to 3-CNF SAT? [closed]

I get how to reduce 3-SAT to 3-COLOR, but I'm not sure how to do it the other way around. Does anyone have any hints or insight?
5
votes
1answer
108 views

Is Hamiltonian path NP-hard on graphs of diameter 2?

Let $G$ be a graph of diameter 2 ($\forall u,v\in V: d(u,v)\leq2$). Can we decide if $G$ has Hamiltonian path in poly time? What about digraphs? Perhaps some motivation is in place: the ...
1
vote
2answers
50 views

Concrete and simple applications for bipartite graphs [closed]

I am looking for concrete and simple problems that may be solved using bipartite graphs or bipartite graph properties. Any idea along with explanations are welcome.
0
votes
0answers
40 views

Marriage algorithm that maximizes number of pairings

I have a bipartite graph similar to the marriage problem, where there are M males and N females, and a 1:1 matching between males and females is desired (with the remainder of the more populous gender ...
2
votes
1answer
90 views

Control flow graphs - Tree decomposition

Considering above terminologies for drawing control flow graphs for any program, it is very simple. For example : While A if B do .. else do .. end while For ...
0
votes
1answer
41 views

Recognizing interval graphs--“equivalent intervals”

I was reading a paper for recognizing interval graphs. Here is an excerpt from the paper: Each interval graph has a corresponding interval model in which two intervals overlap if and only if ...
2
votes
1answer
27 views

Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths

Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut ...
2
votes
2answers
122 views

What is the difference between maximal flow and maximum flow?

What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a ...
3
votes
1answer
297 views

Possible to connect arbitrary number of dots without intersections?

A (now closed) question on SO made me think about the following problem: Given an arbirtary number of points (2D), draw a path that consists of straight lines between points, visits each point ...
4
votes
1answer
53 views

Construct a digraph given its in-degree and out-degree distribution

Could anyone help me with this algorithmic problem: Given the in and out degrees of a set of vertices, is it possible to determine if there exist a valid graph respecting this constraint? The graph ...
2
votes
2answers
183 views

Minimum path between two vertices passing through a given set exactly once

Suppose I have a source node $S$, destination node $D$ and a set $A$ of intermediate nodes $P_1, P_2, \dots$ in an edge-weighted undirected graph. I want to find the vertex $P_i\in A$ that minimizes ...