Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
votes
1answer
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-...
1
vote
1answer
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? ...
7
votes
4answers
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-...
1
vote
0answers
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 ...
2
votes
2answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
5
votes
3answers
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 ...
6
votes
1answer
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 ...
2
votes
2answers
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 ...
0
votes
0answers
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?
7
votes
2answers
54k views

How many edges must a graph with N vertices have in order to guarantee that it is connected? [duplicate]

Possible Duplicate: Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected At lesson my teacher said that a graph with $n$ vertices to be certainly connected should have $ ...
11
votes
1answer
3k views

Directed union-find

Consider a directed graph $G$ on which one can dynamically add edges and make some specific queries. Example: disjoint-set forest Consider the following set of queries: ...
1
vote
2answers
2k views

Does the DFS algorithm differentiate between an ancestor and a parent while computing back edges?

Below is the general code for DFS with logic for marking back edges and tree edges. My doubt is that back edges from a vertex go back and point to an ancestor and those which point to the parent are ...
1
vote
1answer
1k views

What edges are not in any MST?

This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed. Consider a weighted undirected graph....
23
votes
3answers
10k views

Retrieving the shortest path of a dynamic graph

I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is ...
14
votes
1answer
7k views

Efficient algorithm for retrieving the transitive closure of a directed acyclic graph

I'm trying to solve a graph problem (it's not for homework, just to practice my skills). A DAG $G(V,E)$ is given, where $V$ is the set of vertices and $E$ the edges. The graph is represented as an ...
15
votes
1answer
13k views

Find the Simple Cycles in a Directed Graph

This problem, for me, looks very interesting. It was about to find a simple cycle (i.e. cycle where are not repeat nodes) in a directed graph. My solution is going like this, i.e, this graph is a ...
8
votes
1answer
3k views

Algorithm to find all 2-hop neighbors lists in a graph

Given a graph $G = (V,E)$, where $|V| = n$. What is a fast algorithm for generating the collection of all 2-hop neighborhood lists of all nodes in $V$. Naively, you can do that in $O(n^3)$. With ...
2
votes
1answer
1k views

Prove the following problem is NL-complete

Suppose $$A = \left\{\langle G, d, s, t\rangle \;\Bigg|\; \begin{array}{l} \text{\(G\) undirected}, \\ \text{\(s\) and \(t\) are nodes in \(G\)}, \\ \text{there is a path of length \(d\) from \(...
3
votes
1answer
3k views

2OPT Approximation Algorithm for Multiway Cut Problem

In the multiway cut problem, the input is an undirected graph $G= (V, E)$ and set of terminal nodes $s_1, s_2,\ldots s_k$ are in $V$. The goal is to find a minimum set of edges in $E$ whose removal ...
12
votes
4answers
6k views

Transitive reduction of DAG

I am looking for O(V+E) algorithm for finding the transitive reduction given a DAG. That is remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still ...
5
votes
1answer
459 views

Showing that Independent set of size $k$ can be decided using logarithmic space

An independent set $I$ is a subset of the nodes of a graph $G$ where: no 2 nodes in $I$ are adjacent in $G$. For natural number $k$, the problem $k-\text{IND}$ asks if there is an independent set of ...
20
votes
2answers
27k views

Getting negative cycle using Bellman Ford

I have to find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name ...
2
votes
1answer
329 views

Matching girls with boys without mutual attraction (variant of maximum bipartite matching)

Let us say you have a group of guys and and a group of girls. Each girl is either attracted to a guy or not, and vice versa. You want to match as many people as possible to a partner they like. Does ...
3
votes
1answer
377 views

How many random walks to start from each node?

Assume that we are given a real life graph, DBLP network in my case, where degree distribution of nodes follows a power law (many nodes have 1, 2 neighbors, and only a few nodes have hundreds of ...
2
votes
1answer
4k views

Depth First Search to find Minimum spanning tree

A depth first search produces a spanning tree. If you perform DFS using all possible orderings of the adjacency list, wouldn't you find the minimum spanning tree? In other words, there is no example ...
7
votes
1answer
1k views

Algorithms for graph generation using given properties

There may be a large number of algorithms proposed for generating graphs satisfying some common properties (e.g., clustering coefficient, average shortest path length, degree distribution, etc). My ...
8
votes
1answer
227 views

Can Santa be both fair and efficient?

As the net-evergreen The Physics of Santa establishes, it is physically impossible for Santa to get a gift to every kid on the planet. Route planning won't help much there, but can a good planning ...
0
votes
1answer
2k views

Breadth First Search with cost

Looking for some tutorials / references that discuss Breadth First Search that takes into consideration the cost of paths, but could not find much information. Could someone refer a tutorial?
6
votes
0answers
406 views

Shortest path in graph - upgrade an algorithm

We are given a graph with $n$ vertices, $m$ edges, and path edge costs of $x$. For vertices without a direct path that are distant exactly one neighbor, we can add new edge with edge cost $y$. Our ...
1
vote
0answers
120 views

Is it possible to analyse computation?

Take a Turing machine, with a terminating program, convert it to some representation of the machine which captures, in a lossless manner, its state as it performs the computation. So you have a ...
4
votes
0answers
618 views

What is the complexity of Hoffman and Pavley's Nth best path algorithm?

I am currently working on a project where I'm using an implementation of Hoffman and Pavley's "Method for the Solution of the Nth Best Path Problem" to find n-th best path through a directed graph. ...
3
votes
1answer
375 views

Graph Closeness - Different result with gephi and NodeXL

I'm writing a JavaScript library for calculating graph measurements such as degree centrality, eccentrality, closeness and betweenness. In order to validate my library I use two exist applications ...
3
votes
2answers
3k views

Is the clique problem NP-complete also on bipartite or planar graphs?

We know that the clique problem is NP-complete. Is the restriction of the problem to bipartite graphs or planar graphs still NP-complete?
2
votes
1answer
2k views

Base of logarithm in runtime of Prim's and Kruskal's algorithms

For Prim's and Kruskal's Algorithm there are many implementations which will give different running times. However suppose our implementation of Prim's algorithm has runtime $O(|E| + |V|\cdot \log(|V|)...
7
votes
1answer
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 ...
4
votes
2answers
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 ...
3
votes
2answers
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 ...
5
votes
3answers
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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?
3
votes
1answer
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 ...
6
votes
1answer
185 views

Chromatic polynomial of a cycle - Interpreting its terms

I am learning about graph coloring. One of the exercise problems(grimaldi) led me to derive the chromatic polynomial for any cycle($C_n, n \ge 3$). $P(C_n, \lambda) = (\lambda - 1)^n + (-1)^n(\lambda ...
8
votes
2answers
1k views

How to find the vertices on simple path between two given vertices in a directed graph

Given a directed graph and two distinct vertices S and T, is there a polynomial-time algorithm which finds every vertex which is on at least one simple path from S to T? It is not difficult to find ...
9
votes
2answers
531 views

Size of Maximum Matching in Bipartite Graph

Am I correct in my observation that the cardinality of the maximum matching $M$ of a bipartite graph $G(U, V, E)$ is always equal to $\min(|U|, |V|)$?
28
votes
2answers
555 views

How to efficiently determine whether a given ladder is valid?

At my local squash club, there is a ladder which works as follows. At the beginning of the season we construct a table with the name of each member of the club on a separate line. We then write the ...
3
votes
2answers
2k views

Finding odd directed circuit

I want to write an algorithm to find whether a directed circuit whose length is odd exists in a strongly connected digraph. Can anyone help me how to proceed with this problem???
4
votes
0answers
2k views

Show that the Minimum spanning tree Reduce Algorithm runs in O(E) on sparse graphs

This is a problem from CLRS 23-2 that I'm trying to solve. The problem assumes that given graph G is very sparse connected. It wants to improve further over Prim's algorithm $O(E + V \lg V)$. The idea ...
2
votes
1answer
79 views

Given a mechanical assembly as a graph, how to find an upper bound on number of assembly paths

The rules are that you can only build from an existing part, so in the example below, B is the only option for the first move = A. A mechanical assembly might be represented as follows: ...