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
votes
0answers
14 views

Number of nodes to be expanded for DFS, BFS and Iterative-deepening search

I was wondering given depth d and branching factor b and maximum depth m, what would be the minimum and maximum nodes to be expanded for BFS, DFS and iterative-deepening search with cut off d with ...
2
votes
1answer
48 views

The number of maximal independent sets

An independent set is a set of vertices in a graph, no two of which are adjacent. A maximal independent set is an independent set that you can not add any vertex. I want to know if the number of all ...
0
votes
1answer
11 views

Modified Bellman Ford to find minmum cost cycle in O(E²V) time?

I'm thinking about how you can modify Bellman Ford a bit to calculate the minimum weight cycle in an undirected graph with positive weights. Note that the constraint is that the algorithm must run in ...
1
vote
1answer
69 views

Are all adjacency matrices represented by 0 and 1s?

Are there any cases when adjacency matrix should have entries other than 0 and 1?
0
votes
1answer
22 views

Unclear about proof for unique MST given graph G with distinct weights

http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/mst.pdf I have some trouble understanding the proof above. I understand that we assuming two MSTs, T and T', and an edge e that is the ...
5
votes
3answers
173 views

How to choose the maximum number of nodes (with constraints) from a graph

Consider a connected undirected acyclic graph $G$ with $n$ nodes and $n-1$ edges. The nodes have non-negative integer weights less than $n$. A positive integer $x$ is given and you want to choose at ...
0
votes
1answer
56 views

Dijkstra single-source shortest path $\Omega(n\log n)$?

If I have a directed graph with $n$ weighted edges, is it possible to prove that Dijkstra's single-source shortest path algorithm takes $\Omega(n\log n)$ in the worst case? I know heaps reduce ...
0
votes
2answers
25 views

Bellman–Ford negative path meaning

In the Bellman–Ford algorithm, what is the practical meaning of having a negative path between routers? I have tried searching the net but didn't find any data thanks Eli
0
votes
0answers
19 views

Evaluation in community detection

I took some evaluation metric as list in lab41.github.io/Circulo/ , and I have some doubts understanding them. as listed in the link above : Conductance, Internal density,expansion, ...
-1
votes
0answers
16 views

Tournament graph

I have to prove the following assertion: given a tournament graph with $n$ vertices, $n\geq 5$, there can be made an arrangement of the arcs such that between any two vertices exists at least one way ...
2
votes
2answers
39 views

Difference between edges in Depth First Trees

I have a directed graph, where each node has an alphabetical value. The graph is to be traversed with topological DFS by descending alphabetical values (Z-A). The result is $M,N,P,O,Q,S,R,T$ (after ...
0
votes
0answers
23 views

Algorithms for verifying and solving three-coloring [duplicate]

I found the following problem that I am trying to answer: Consider the three color problem where V, vertex set of a bipartite graph. can be partitioned into three subsets such that there is no ...
1
vote
0answers
27 views

Getting ALL negative weight cycles of a graph using Bellman-Ford

I'm doing a min cost assignation problem to assign doctors to their working days for a hospital. After correctly getting the max flow with Ford-Fulkerson algorithm, I would like to use the cycle ...
5
votes
2answers
99 views

Is Dijkstras algorithm used in modern route-finding systems?

Is Dijkstra's algorithm used in modern route-finding systems such as Google maps or the satnav in your car? If not, then what is?
0
votes
1answer
35 views

All but Five Three Colorable

An NP Problem Named All But Five Three Colorable(AB53C) is defined as follows :- Input : Connected Graph G(V,E) The Connected Graph is AB53C, iff the Given Graph is 3-Colorable by leaving UPTO 5 ...
1
vote
1answer
50 views

Questions on Topological Sorting

Currently learning about topological sorting. My teacher gave us this problem. The answer given to us is : B,A,C,E,D,G,F,H in lexicographical order. Why does the order go from B,A,C THEN go to E ...
-1
votes
1answer
23 views

How to find a minimum cut of a network flow?

I am currently reading the lecture slides from Princeton regarding network flows but I cannot understand how they manage to find out minimum cuts from a directed graph. Could someone explain how ...
3
votes
1answer
78 views

Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle. Define the directed cycle mean cost to be $\frac {\{\text {sum ...
1
vote
0answers
33 views

Set of points partitioned into max subsets of size N with no intersecting edges

Question Given a set of X kd (k-dimensional) points, find the maximum number of closed subsets of these points such that no subsets (each forming a convex hull) overlap or intersect, that each subset ...
0
votes
1answer
37 views

Vertex Cover of size k in a tree?

What is a polynomial time algorithm for finding a vertex cover of size $k$ in a tree? Would depth first or breadth first search be efficient or is there some other algorithm that finds the vertex ...
3
votes
2answers
42 views

Find a MST such that it's mostly red (original graph's edges are colored red and blue)

Consider the following problem: Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight). Find an ...
7
votes
0answers
47 views

Compute a max-flow from a min-cut

We know that computing a maximum flow resp. a minimum cut of a network with capacities is equivalent; cf. the max-flow min-cut theorem. We have (more or less efficient) algorithms for computing ...
1
vote
1answer
43 views

find the shortest path between two nodes where the number of edges is minimal [closed]

Say you are given an undirected unweighted graph, where s and t are nodes from the graph. d(s,t) means the distance between s and t which outputs the number of edges. How do I find the the maximum ...
3
votes
0answers
45 views

Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph?

Usually questions deal with claw-free graphs, but suppose we are given a graph $G$ and there are $k$ vertex-disjoing claws in the graph, how can we derive a randomised algorithm using color coding to ...
5
votes
0answers
34 views

Are there Some Pairs Shortest Paths Algorithms?

I know that there are All Pairs Shortest Paths algorithms. But I am not sure if they are effective if I am trying to solve the Pairs-Shortest-Path problem for a subset of my vertexes. The properties ...
2
votes
1answer
82 views

Find a subgraph whose edge weights sum to at least the number of nodes

Given a graph G = (V,E) every edge is assigned a real number Xe $\in$ [0,1] The sum of x variables for all edges is equal to the number of edges -1 : $\sum x_V = |V|-1$ For a subset S ...
0
votes
2answers
40 views

Why is the complexity of the BFS O(V + E)?

Consider the algorithm (from another question): ...
7
votes
2answers
274 views

What is the most efficient algorithm and data structure for maintaining connected component information on a dynamic graph?

Say I have an undirected finite sparse graph, and need to be able to run the following queries efficiently: $IsConnected(N_1, N_2)$ - returns $T$ if there is a path between $N_1$ and $N_2$, ...
-2
votes
0answers
30 views

How to find the spanning tree with a weight next higher than the minimum?

In some places where this question occurs it seems that this makes sense only if all the edge weights are distinct. Can someone help with what is going on here?
1
vote
1answer
54 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
0
votes
0answers
5 views

Get field/branch of science by keywords [migrated]

In hindsight of my MSc Thesis, I realize that a majority of my time was wasted on trying to fit my problem in some subfield, only to realize it was often not a good fit. An underlying cause is the ...
0
votes
0answers
16 views

Symbolic formalization of a rooted directed subgraph

In a directed graph $G(V, E)$; how can I define in symbols the set of subgraphs $G'=(V',E')$ of $G$ such that $G'$ has a root vertex, i.e., a vertex that sends a directed path in $G'$ to every $v\in ...
1
vote
1answer
20 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
46 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
64 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 ...
5
votes
1answer
152 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
26 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
38 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
25 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
50 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
37 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
61 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
63 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
26 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
56 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
46 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
37 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
27 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
36 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 ...