Tagged Questions

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
16 views

Construction of graph with given Wiener Index

Given the sum of weights of shortest paths between all vertices in a graph, how can I construct a connected graph that satisfies the given sum? That is, how can a graph with a given wiener index be ...
0
votes
0answers
26 views

Finding negative weight cycles in graph using BFS/DFS

I was learning about Bellman-Ford in CLRS and in the exercises, there is a question to find a way to list the vertices of a negative weight cycle if one exists. I was able to find one algorithm by ...
2
votes
0answers
58 views

I need a better data structure than a graph with condition nodes

Suppose i have a cyclic weighted ($\mathbb{Z}$) directed graph where nodes are either simple or complex. a simple node is just a usual node whilst a complex node is a node that contains a set of ...
4
votes
1answer
124 views

Proof of Dijkstra Algorithm Optimality

Has it been proven that Dijkstra's algorithm is optimal for asymptotic worst case of single-source shortest path on directed graphs? (Assume no preprocessing) I became curious when Wikipedia ...
2
votes
0answers
20 views

Common subgraph isomorphism with K vertex

I'm looking for subgraph isomorphism of at least K vertex between Graph A and B. I only can come up with the dumbest algorithm, which is: Compute all combination of vertices with length K of Graph ...
2
votes
1answer
37 views

Enumerating programs as graphs, or executing graphs?

Graphs have nodes connected together by edges, for example (not directed, not including connecting nodes to themselves, or multiple connections between the same two nodes) 2 graphs exist with 3 nodes, ...
2
votes
1answer
21 views

Complexity of Independent Set on Triangle-Free Planar Cubic Graphs

I know that IS (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and IS on triangle-free graphs is also NP-Complete. But how about IS on triangle-free planar ...
-1
votes
0answers
45 views

Modify Johnson's algorithm

Let's say we modify Johnson's algorithm to use a different reweighing scheme. Let $w^* = \min_{(u,v) \in E} {w(u,v)}$. Define the new weight function as $w'(u,v) = w(u,v) - w^*$ for all $(u,v) \in ...
-3
votes
0answers
24 views

Adding, deleting, increasing and decreasing edges of MST graph

Suppose we have found a MST of a graph. Then the graph undergoes some change. For each of the following changes to the initial graph, describe an efficient algorithm to update the MST (the ...
4
votes
2answers
53 views

Vertex cover in bipartite graph from Hopcroft-Karp Algorithm

Vertex cover in bipartite graph is polynomial algorithm: by König's theorem the number of edges in a maximum matching is the number of vertices in a minimum vertex cover. I've implementated the ...
0
votes
0answers
32 views

Cycles in graphs with optional edges, redux: labelled optional edges

In a previous question, I asked how much information is needed to encode the possible cycles in a directed graph with $N$ "optional" edges given only the subset of the optional edges that are present ...
0
votes
1answer
54 views

Longest Path in a directed rooted graph

A directed rooted graph is defined as graph for which there exists a vertex r such that to every vertex x there is a unique path (Equivalently dfs tree with source r has only back edges and has all ...
0
votes
1answer
18 views

How do deal with the following situations using Prim's algorithm?

Consider the following Graph We want to generate the MST using Prim's algorithm. Starting from node A, suppose we pick B as our next node, we see a self-loop that has less weight than the two other ...
1
vote
1answer
48 views

Hungarian Assignment Algorithm Implementation

I want to implement the "vertex similarity" algorithm described in the paper Graph Isomorphism Detection Using Vertex Similarity Measure. The algorithm is as follows: ...
2
votes
1answer
42 views

Characterizing cycles in a directed graph with optional edges

Consider a directed graph in which some edges are marked as "optional". A graph with $N$ optional edges induces a family of $2^N$ graphs depending on which edges are removed. In some cases, some of ...
-1
votes
1answer
26 views

Finding a maximum-diameter tree in an undirected unweighted graph

The diameter of a graph is the largest of all shortest-path distances in it. How can we find a tree of maximum diameter within an undirected unweighted graph? Note that the tree does not have to be a ...
0
votes
1answer
19 views

Betweenness centrality measurement ignoring inverse paths?

I'm implementing the Betweenness Centrality algorithm proposed by Brandes (first algorithm on this paper - also below), and I'm running into a very weird issue: it seems to be ignoring some paths ...
1
vote
1answer
28 views

Is the maximum coverage variant of Vertex Cover also NP-hard?

In Chapter 3 of "Approximation Algorithms for NP Hard Problems" edited by Prof. Dorit S. Hochbaum, there is such a sentence that "Maximum Coverage Problem is clearly NP-hard, as Set Cover is reducible ...
0
votes
1answer
22 views

Bayes nets - calculating probabilities

Given a Bayesian network, say a -> b -> c, all binary random variables (I won't show the CPTs, assume they are given). You are told b and c are true. How do you calculate the P(a=True)?
1
vote
1answer
60 views

Find a 3-colouring using the 3-colourability decision problem

I was learning about NP problems. I read that for many problems, like Clique, we can easily convert its decision problem to derive a solution of search problem. (For Clique problem, you only need to ...
0
votes
0answers
23 views

Canadian traveller problem on directed acyclic graphs

What is the complexity of the Canadian traveller problem variant where the only thing that is seen is a single node ahead on a directed acyclic graph so that we cant go back once we go to a new node ...
0
votes
0answers
23 views

Merging two disconnected graphs

Firstly, I'd like to apologize for any misused terms or ways I could have made the description much more succinct. It's been a while since I took machine learning during my bachelor's. I have two ...
0
votes
1answer
43 views

Reference request for coding Knight's Tour

Could someone give an easily accessible reference containing an algorithm that could be conveniently implemented into a code for computing Knight's Tour (preferably also with fairly good efficiency)?
-2
votes
1answer
22 views

Strongly connected components in graph

Statement:SCC in G is same as Rev(G) Ex:Consider the following graph g 0->1 1->2 2->4 3->1 4->3 The strong components set would be S={0,1,2,3,4} If I reverse the above graph (i.e) 1->0 1->3 ...
-1
votes
1answer
50 views

Relative Importance in Graph Theory

I am working on an algorithm that ranks a set of nodes in a graph with respect to how relative this node is to other predefined nodes (I call them query nodes). The way how the algorithm works is ...
-2
votes
1answer
13 views

List the edges (vertex pairs) of a minimum spanning tree for this graph in the order they would be chosen by Prim's algorithm

List the edges (vertex pairs) of a minimum spanning tree for this graph in the order they would be chosen by Prim's algorithm Please help me to understand and complete this. I would very much ...
2
votes
1answer
37 views

Split-Find: maintaining dynamic graph connectivity information, under edge deletion

Is there a data structure to keep track of the connected components of a dynamic graph, when the graph might by changing by deleting edges of the graph? Let $G$ be an undirected graph. I have two ...
0
votes
1answer
60 views

What is the difference between shortest distance and shortest path?

I am studying graph currently. I found a question, which asks for The List A[] which shows shortest distances between $V$ and every other vertex The List ...
0
votes
1answer
130 views

minimum spanning tree and minimum heavyweight spanning tree

a minimum heavyweight spanning tree is a spanning tree in which the heaviest edge is as light as possible. Formally, input : given connected undirected weighted graph, $G$. output : a spanning tree ...
-1
votes
1answer
25 views

Triangles incident on a vertex (Graphs)

I have a project that I am doing. The specification requires specific methods on a graph class. Two of the methods requires this: ...
-2
votes
1answer
80 views

Finding bridge edges more efficiently than Tarjan's algorithm [closed]

I have to find a bridge edge in a graph but have to find it efficient time complexity. Is there an algorithm that is better than Tarjan's Bridge-finding algorithm?
-1
votes
1answer
36 views

Understanding A* Search on Tropical Island

I am working on an online course on AI and I am now working to understand A* better. Basically, right now I am working on a problem where: we live on a tropical island and we're trying to navigate ...
0
votes
1answer
42 views

Union grouping in bipartite graphs?

I'm trying to figure out a good (and fast) solution to the following problem: I have two roles I'm working with, let's call them players and teams having many-to-many relationship (a player can be on ...
2
votes
2answers
46 views

Finding paths of certain length in trees

In a graph tree, is there any "smart/existing/efficient" algorithm to find linear segments of defined length? For example given a tree graph: ...
3
votes
1answer
89 views

Finding the minimum number of calls in a tree

I was asked this question in an interview and struggled to answer it correctly in the time allotted. Nonetheless, I thought it was an interesting problem, and I hadn't seen it before. Suppose you ...
1
vote
0answers
22 views

Why is it that in a butterfly network, there is a unique path from the input to the output?

Consider the a butterfly network as defined on the following OCW notes on page 208. An explantation of it can also be found on the following page. I was wondering if someone had a proof or an ...
1
vote
2answers
57 views

For a graph to be connected, you need at least n-1 edges rigorous proof

This fact seems obvious but I was unsure how to go about proving it very rigorous. Let $|V| = n$ and $|E| = m$ for some connected graph $G$. Then consider the following proposition: If a graph is ...
1
vote
1answer
17 views

Why do Benes networks form bipartite graphs when you build a constraint graph for them?

I was learning about Benes networks and was wondering why they formed bipartite graphs (and thus are two colorable) when one draws a constraint graph for them. The constraint graph is based on the ...
1
vote
0answers
57 views

Influence of edge number and priority-queue implementation on the runtime of Dijkstra

When we try to find the shortest path of a directed weighted graph using Dijkstra’s algorithm, is there a relation between the number of edges/vertices of the graph and the different implementations ...
8
votes
1answer
91 views

What is the name of the problem? (partitioning graph into three covers)

I was wondering if this problem has a name: Given a simple graph whose edges are colored red, blue and green, $G=(V,B\cup R\cup G)$, is there a vertex-coloring $c:V\to \{B,R,G\}$ such that every edge ...
1
vote
0answers
30 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
112 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
vote
1answer
41 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
42 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
69 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
27 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
55 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
49 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
49 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
3answers
96 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 ...