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
0answers
27 views

Algorithm to generate graph of specific known form

I am trying to generate a graph (the structure with edges and nodes), that as a structure like an Order-7 triangular tiling of specified diameter around a central node. ...
2
votes
2answers
86 views

Finding an exactly weighted st-path in a digraph

I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic. The question is: given 2 nodes $v_1$ and $v_2$, is there a ...
-1
votes
0answers
23 views

importance of graph theory in software testing [closed]

I know that it is important part of the software testing and computer science but I am not able to find any data related to my question on googling. how is the graph theory related to software ...
1
vote
1answer
34 views

Betweenness Centrality measurement in Undirected Graphs

I'm working with graphs of a very large size (> 60k vertices), and want to speed up B.C. measurements. It is defined here: http://en.wikipedia.org/wiki/Betweenness_centrality The algorithm that I am ...
0
votes
0answers
39 views

smaller size approximation to minimum vertex cover

Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum? Usual algorithms seems to aim to find an approximation such that ...
6
votes
1answer
63 views

Implementing general vertex folding procedure in an undirected graph

I'm implementing the algorithm presented in "Improved Parameterized Upper Bounds for Vertex Cover" paper (PDF). I'm a bit stumped by the General-Fold procedure. ...
0
votes
1answer
26 views

minimum vertex set removal for edge-free graph

I'd like to know the name and the algorithm for the following problem which I'm guessing is a classic, but is slightly different from graph connectivity. Consider a undirected graph G=(V,E). What is ...
-1
votes
1answer
49 views

Minimising two maximum edges in s-t path

I've been trying to solve the following problem: Problem is the following: Given a graph and a pair of nodes $s$, $t$ you have to find the path from $s$ to $t$ which minimises the sum of its two ...
1
vote
1answer
42 views

What do we know about covering the edges of a graph by disjoint paths?

Two related things I have heard/know of are, (1) That there exists a polynomial algorithm to find a cover of the vertices by $k$ vertex disjoint cycles. (Can someone give a reference for this?) ...
3
votes
0answers
40 views

Efficient update to rational flow network?

Once we've computed the max flow in a flow network with integral capacities, we can change one of its edges' capacity by a unit and recompute a maxflow in linear time using BFS. Is there something ...
4
votes
2answers
75 views

Decremental reachability in a grid graph

Consider an $n$ by $n$ grid graph. For example, the following. You can of course reach the top left corner from the bottom right. Now consider the graph dynamically with an arbitrary number of ...
2
votes
0answers
84 views

Fastest algorithm for shortest path with atmost k edges on a DAG with non-negative edge weights?

(Please note, this is not a duplicate to Shortest path with exactly $k$ edges OR Shortest path with a fixed number of edges. What I want is a better algorithm) The problem under consideration is to ...
7
votes
0answers
89 views

Change in the distances in a graph after removal of a node

Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that, $$\operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G ...
2
votes
1answer
23 views

connected components - determining “groups” in Go

I would like to write an analysis of go positions. Part of it requires me to determine the "groups" on the board and count their "liberties". Any Go "position" is a collection of black ...
-2
votes
1answer
39 views

doubt regarding power of graph [closed]

could you help me in clarifying a doubt regarding how to find square of a graph g from graph g.the doubt occurs on 15th page of the document which I have shown you by the link given.the doubt is that ...
0
votes
0answers
89 views

Dynamic distance from source in a directed graph (only incremental or only decremental)

At the beginning we have a directed unweighted graph of $n \leq 10^3$ vertices, and $m \leq 10^5$ edges, with some vertex being a source, and we perform updates and queries on it. An update is adding ...
1
vote
1answer
39 views

Performing Transitive Reduction via neighbourhood and strongly connected components

I am trying to learn(self-study, not homework) how to perform transitive reduction according to what what Prof. Leskovec explains in section 10.8.6 in Mining Massive Datasets. The book is free to ...
-4
votes
1answer
49 views

Count of all simple paths between two vertices in a Complete graph [closed]

A path is simple if it repeats no vertices. How many simple paths between two vertices in Complete graph? One way is listing the simple paths is to use depth-first search. but i think it should be ...
11
votes
2answers
64 views

Enumerate all non-isomorphic graphs of a certain size

I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ ...
0
votes
0answers
23 views

A bound for the minimum vertex cover of scale-free graphs

For a complete graph, the size of minimum vertex cover is $n-1$. I was wondering whether there exist an upper bound (or an expected value or upper bound) for the size of minimum vertex cover for ...
3
votes
0answers
31 views

Applications of min spanning trees

What are the significant applications of minimum spanning trees? After doing some research online and in several textbooks, I have found three real-world applications: Building a connected network. ...
4
votes
1answer
53 views

Algorithm to find most nodes in distinct cycles

I am trying to design a program where people trade objects within a fixed set of objects. They offer a single product, and designate a set of products they are willing to accept for that product. ...
0
votes
1answer
42 views

Why BFS is source vertex specific? [closed]

Take a graph $G=(V,E)$ . As we know both DFS and BFS are graph search algorithms . But why the algorithm for BFS is designed in such a way that it does not cares about the vertices that are not ...
0
votes
1answer
32 views

Inserting vertex in an adjacency matrix

If a graph with $v$ vertices is represented in the form of adjacency matrix . Then, adding a new vertex to the existing graph requires how much time ? Is it $O(v^2)$ or $O(2v)$ . We have the ...
0
votes
1answer
68 views

Can I use breadth-forst search for topological sorting?

Can I use Breadth first Search for finding topological sorting of vertices and strongly connected components in a graph? If yes how can I do that? and If not why not? I tried with a simple acyclic ...
-2
votes
1answer
19 views

How to figure out the minimal number of colors needed to color specific given graphs?

I found this question on the net and I'm wondering what is the process for answering such questions? I assume there is some formula that works for all graphs? 1.a. Consider the undirected graph with ...
2
votes
2answers
49 views

Is it possible to implement a Neural Network using a graph data structure?

I'm trying to implement a feedforward neural network using a graph. The thing is: I haven't found any example in which is used a graph data structure. So far the examples I've found used arrays. Can ...
1
vote
0answers
28 views

Upper Bounds on Characteristic Path Length of Graphs

Characteristic (average) path length is defined here: http://cs.stackexchange.com/a/7538/20256 I want to establish upper and lower bounds on the CPL for a graph of $n$ vertices, and any positive ...
3
votes
1answer
63 views

Bellman-Ford and zero-distance cycle

Problem statement: Given a graph G(V,E) which is not acyclic and may have negative edge weights (and thus may possibly have negative-length cycles), how does one detect if the graph has a zero-length ...
1
vote
0answers
73 views

Finding the number of distinct maximal matching in a bipartite graph [closed]

In a bipartite graph, how can we find the total number of ways of getting a maximal matching? The cardinality of both the sets in the bipartite graph may not be the same. So two matchings are said to ...
3
votes
2answers
94 views

Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size

There is a complete graph $G$ with $n$ vertices and each edge has a distinct weight. Is there an efficient (not necessarily optimal) algorithm to select $k$ vertices from the graph $G$, such that the ...
2
votes
1answer
34 views

Choice of algorithm for hierarchical clustering for minimizing network communication costs

Suppose I have a large distributed task running on a cluster system where part of the workload is compute bound and part depends on network performance. Data transfer is not completely homogeneous ...
2
votes
0answers
33 views

Stopping condition for goal-directed bidirectional search for shortest path

So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*. So let $l(u,v)$ ...
0
votes
1answer
187 views

Is it possible for a graph to have two different minimum spanning tree

I am suppose to create a minimum spanning tree from this graph below I got this answer However this is my textbook answer Based on what i have learnt , I think my answer and the textbook ...
1
vote
1answer
58 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
59 views
5
votes
2answers
156 views

Adding a node between two others, minimizing its maximum distance to any other node

We are given an undirected graph weighted with positive arc lengths and a distinguished edge $(a,b)$ in the graph. The problem is to replace this edge by two edges $(a,c)$ and $(c,b)$ where $c$ is a ...
3
votes
1answer
73 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
57 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
51 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
135 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
74 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 ...
4
votes
1answer
119 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
22 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
33 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
125 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 ...
0
votes
2answers
132 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
36 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 ...
1
vote
2answers
83 views

How can I compute the average weight of an undirected graph?

Given a weighted, undirected graph $G = (V,E)$, how can I compute the average weight of edges? It seems an easy problem (divide the total weight to the number of edges!) but I couldn't manage to find ...
4
votes
1answer
117 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 ...