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)

3
votes
0answers
10 views

Determining if $G$ contains $K_4$ as a minor in polynomial time

I am trying to devise an algorithm for determining if an undirected graph $G$ contains $K_4$ as a minor. I was able to show in a previous problem how to test for $K_{2,3}$ by looking at all pairs of ...
0
votes
0answers
11 views

Find equivalent weighted DAG sum of whose weight is minimum

When a given weighted directed acyclic graph represents some object flow, what is the most efficient algorithm to find the equivalent graph sum of which edges is minimum? Here, 'equivalent' means the ...
5
votes
1answer
93 views

Maximum chromatic number of sparse graphs

It is well-known that the chromatic number of a graph can be as high as $n$. But what is the maximum chromatic number of a graph with $m = O(n)$?
0
votes
2answers
29 views

Listing all possible train routes

I'm interested whether there is the standard solution to the following problem. Some number of train routes is given: Route1: First City -> Next City -> ... -> Last City Route2: ... ... We need to ...
0
votes
1answer
20 views

Reweight general weighted graph to distinct graph for using Borůvka's

Is it possible to re-weight a generally-weighted graph to a distinctly-weighted graph to apply Borůvka's algorithm (wiki) for minimum spanning tree to it? I can't seem to think of a way to make a ...
3
votes
0answers
17 views

Birkhoff-von Neumann theorem for bistochastic digraphs

A weighted digraph (with loops) is bistochastic, iff the weights are non-negative, for all non-sink nodes, the sum of the edge weights of the out-edges is $1$, and for all non-source nodes, the sum ...
1
vote
1answer
113 views

Algorithm to find shortest path between two nodes

I want an algorithm similar to Dijkstra or Bellman-Ford for finding the shortest path between two nodes in a directed graph, but with an additional constraint. The additional constraint is that ...
1
vote
1answer
62 views

How can I evaluate an algorithm for a NP-Hard problem?

I have written a program to calculate the number of stable partition in a graph. ( That is: find which partition of the nodes does not have edges between nodes of the same block. ) The professor, ...
0
votes
1answer
18 views

Articulation vertex in complementary graph

I need to implement an algoritm, but I can't understand the theory behind it. How can I prove that if v is an articulation vertex in a graph G , that it will not be an articulation vertex in G' ...
2
votes
0answers
33 views

Constructing orthogonal latin square Parker/Knuth method

I'm working through Knuth; The Art of Computer Programming, Vol. 4 Fascicle 0 and I'm having a little trouble making sense of the method Knuth describes for computing an orthogonal latin square. The ...
0
votes
0answers
29 views

Finding and Grouping like children

I'm working on a dependency managemen solution for a JavaScript. I'm trying to find the best pattern for grouping similar items in a graph into their own 'modules'. Given a dependency tree like ...
2
votes
0answers
48 views

What is a best known algorithm for finding diameter of undirected graph?

What is best known algorithm (approximate or exact) for finding diameter of a large undirected graph? The diameter is defined as longest of shortest paths between any two nodes. I know that naive ...
2
votes
1answer
33 views

How to correctly contract an edge in a network?

Assuming an adjacency list as data structure of a directed Graph, it is not completely clear to me how "contraction of an edge" is defined. Let me cite the definition I do have at hand: Source: ...
1
vote
1answer
45 views

Anagrams solver based on transitions probability

I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible ...
1
vote
2answers
301 views

Proving that a certain graph contains a 4-cycle

Show that if $G$ is a graph with $|E| \geq 2|V|^{3/2}$, then $G$ must contain a $4$-cycle Can someone explain/point me in the right direction on this? Let's say we say $|V|= 4$, using the ...
2
votes
1answer
23 views

Transform unstructured flow charts into structured ones

Has anyone studied the problem of converting a generic flowchart to a semantically equivalent "structured flowchart" (i.e. one that only uses the 'if' and 'while' block structure)? I can see this ...
1
vote
0answers
53 views

Maximum flow problem with non-zero lower bound

Given $G = (V,E )$ a directed graph, if $ X \subseteq V $ we write $$\begin{align*} \delta ^{+}(X) &= \{ xy\in E \mid x \in X, y\in V - X \} \\ \delta ^{-}(X) &= \delta ...
1
vote
0answers
47 views

Borůvka cleanup in linear time?

Given boruvka's algorithm: ...
3
votes
1answer
64 views

Efficient algorithm to find vertex with paths to every other vertex

$G=<V,E>$ is a directed graph. I need to write an efficient algorithm that finds a $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ ($v$ has a path to every other ...
1
vote
0answers
26 views

Does Edmonds Karp take back-edges into account?

I amb doubting with the implementation of the Edmonds-Karp implementation of the Ford-Fulkerson algorithm. This is a problem with flow networks. As I understand the algorithm, it consists on taking ...
3
votes
1answer
19 views

Do $s$-$t$ cuts partition contingent vertices?

The definition of an $s$-$t$ cut is a partition of the set of vertices $V$ into $2$ sets $(A, B)$ with $s$ in $A$ and $t$ in $B$. My understanding of set partitions is that the positioning of elements ...
1
vote
1answer
66 views

Shortest walk that covers $k$ nodes

I have the following problem, I would like to know an efficient algorithm to solve it. Suppose I have a weighted graph $G$ and a set of vertices $K$, I want to find a walk which starts at a vertex ...
0
votes
1answer
57 views

kth nearest vertex in a unweighted graph

Given an unweighted undirected graph $G$ with $10^5$ vertices and a subset $S$ of special vertices and an integer $k$, I want to find the $k$th nearest special vertex for each vertex. What algorithm ...
1
vote
0answers
50 views

Enumerate subtrees of a given size in a graph

Given a graph $G$ with $n$ nodes, is there an algorithm to find $m$ subtrees, each with $\lfloor n/m\rfloor$ or $\lceil n/m\rceil$ nodes, such that every node of $G$ is in exactly one tree? Other ...
0
votes
0answers
29 views

Find a path in a complete graph with cost limit and max reward

I'm looking for an algorithm to solve this problem. I have a region in which there are several areas identify by its id and x,y,z position. I've made a graph in which each vertex identifies one ot ...
2
votes
1answer
54 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
19 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
76 views

Are all adjacency matrices represented by 0 and 1s? [closed]

Are there any cases when adjacency matrix should have entries other than 0 and 1?
0
votes
1answer
25 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
191 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
75 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
27 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
35 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, ...
0
votes
1answer
41 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
41 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 ...
1
vote
0answers
25 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
30 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
116 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
58 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
25 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
83 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
45 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
40 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
48 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
59 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
51 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 ...
5
votes
1answer
71 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
36 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
85 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 ...