# Questions tagged [graphs]

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

2,100 questions
500 views

### Bellman-Ford: shortest path

my assumption: - we have an undirected graph with only positive edges - the edges are sorted alphabetically:     e.g A-B, A-C, B-D     and e.g not C-A, D-B, A-...
3k views

### Computing the clustering coefficient

I saw in this video that computing clustering coefficient of central node of a star graph using the following algorithm is $\Theta(n^2)$ and for a clique it is $\Theta(n^3)$. is that correct? ...
984 views

### XOR-like behavior in flow networks

XOR is not the correct name, but I am looking for some kind of exclusive behavior. I am currently solving a set of different (assignment) problems by modeling flow networks and running a min-cost-max-...
661 views

### Bellman-Ford algorthm and negative cycle proof

I found the algorithm for finding the negative cycle in a graph after running Bellman-Ford algorithm. The algorithm is to perform another relax iteration over all the edges. Than if we find an edge ...
551 views

### Maximum weight matching

There are polynomial time algorithms to find maximum weighted matching in a general graph. Is there any algorithm that also handles negative weights in the general graph and find maximum weighted ...
243 views

### Coloring a Unicyclic Graph

I am trying to design an efficienct algorithm to color a unicyclic graph. I know if a graph does not contain any cycles (it's a tree) then it is 2-colorable. But cycles are either 2 (is even number of ...
69 views

### Mean number of edges between two equal partitions

For a random undirected graph with $n$ nodes, where each node has $k$ incident edges ($nk/2$ edges in total), the vertex set is partitioned into two sets each having $n/2$ nodes. What is the ...
8k views

### Minimum spanning tree with two minimum edge weights

Given an undirected weighted graph $G$ with two edges of minimum weight and all other edges are distinct. Does G have a unique minimum spanning tree? I know the proof for if all edge weights are ...
1k views

### For what special cases does this vertex cover algorithm fail or work?

I'm trying to find a polynomial time algorithm for finding the minimum vertex cover for a graph. I've written the algorithm below; I know this problem is $\mathsf{NP}$-hard, which means there are ...
1k views

### K-Clique in Connected Graphs

A question about the clique problem (specifically k-clique). Is there any algorithm that takes advantage of the properties of connected graphs to find cliques of a given size ...
68 views

### Can you obtain more than two vertex covers from a bipartite graph using a max-flow algorithm?

Applying a max-flow algorithm to the graph it's trivially possible to find one or two vertex covers, inverting source and sink and the directions of the flows. Is it possible to find more?
54k views

4k views

### Practical applications of disjoint set datastructure

I know that the disjoint set datastructure is used to keep track of the connected components of an undirected graph when the edges are added to the graph dynamically . I also know that is is used in ...
2k views

### Min cost max flow in bipartite run time

I have a bipartite graph with $|E|=O(|V|^2)$, a super-source and a super-sink. I am looking for the min-cost max-flow (the max-flow of all possible max-flows that has the minimum cost). For the sake ...
243 views

### Given many partial orders, check them for consistency and report any that are not consistent

Inputs. I am given a finite set $S$ of symbols. I know there should exist some total order $<$ on $S$, but I'm not given this ordering and it could be anything. I am also given a collection of ...
15k views

### When would best first search be worse than breadth first search?

I am studying best first search as it compares to BFS (breadth-first search) and DFS (depth-first search), but I don't know when BFS is better than best-first search. So, my question is When would ...
4k views

### Does a weighted Breadth First search have “memory” when moving to the next vertex?

I'm in a programming course and one Problem given to us is to mark the order in which BFS visits nodes in a weighted graph. My question is whether BFS adds the distance of the previous path while ...
1k views

### The path between any two nodes in cyclic directed graph

G{V, E} is directed, cyclic, weighted graph. What is the algorithm of finding all paths between any given two nodes? Can you suggest any good reading?
1k views

### If I have sources and sinks of a DAG can I find the minimum number of edges to be added to make it Strongly Connected?

I am trying to create an algorithm in linear time where if given a directed acyclic graph I can add edges to make it strongly connected components. I believe I have an algorithm to identify sources ...