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)

0
votes
0answers
3 views

How to make LALR(1) directly?

I studied LR(1) parsers and then LALR(1) and noticed that if we wanna construct LALR(1), We should FIRST construct the LR(1) parser and then by combining states we can go ahead for LALR(1) parser. ...
0
votes
0answers
2 views

How does constraints of linear program of multi-commodity flow guarantee that commodity will end up in its sink

The multi-commodity flow problem problem statement - wiki According to constraints of multi-commodity flow problem a given material must start at source s with demand d and end up at its target t. ...
2
votes
2answers
17 views

Check whether an undirected graph contains a simple cycle of length four using the “Squares” method

The following problem is exercise 4.3 of the book "Algorithms" by S. Dasgupta, C. Papadimitriou, and U. Vazirani. Squares. Design and analyze an algorithm that takes as input an undirected graph ...
-3
votes
0answers
23 views

Number of ways to construct a Regular graph

For a regular graph (each vertex has same degree k), a part of graph upto level l is given, how to compute the total number of ways in which the graph can be completed given that m edges and n ...
-1
votes
0answers
13 views

Tarjan's Bridge Finding Algorithm Psuedocode? [on hold]

I was looking for a verbose and well-constructed psuedocode for finding Bridges in an undirected Graph. If possible please share any psueodocode, thank you!
0
votes
1answer
43 views

AI : how can i study it by myself? [on hold]

Peace for All I'm interested in studying artificial intelligence, i bought a book "artificial intelligence Modern Approach " But I could not begin to delve into it for some reasons So I need your ...
-1
votes
1answer
32 views

Time complexity for Breadth-First search

I would like to know why the average number of nodes at level d in BFS in a search tree is $\frac{1+b^d}{2}$ as given in this lecture(p.15)?(Here b is the branching factor of the tree and d is the ...
0
votes
1answer
28 views

Shortest distance from a set of points

Consider an unweighted, undirected, simple graph $G=(V,E)$. We have some subset $S \subseteq V$, and we want to determine the shortest distance from any vertex $v\in V$ to some vertex $s\in S$. To ...
1
vote
1answer
34 views

Longest path in a cyclic, directed and weighted graph

I am looking for the longest simple path in a directed, cyclic and weighted graph with positive and negative weights. In my research so far I have found out that you need to generate ...
1
vote
0answers
19 views

Vectorized Algorithm for finding the Shortest Path in a Graph

I know that you can calculate the shortest path in a vectorized fashion using Floyd-Warshall, e.g. like proposed by Han and Kang, however I want the matrix, they call "via", the actual route taken ...
-3
votes
0answers
18 views

Maximum Flow and “eulerian” paths

I am working on the following exercise and I am not able to get any further. Imagine you are responsible for updating the Street View data for Berlin. You have k cars available starting at ...
1
vote
0answers
14 views

Maximum weighted antichain over a DAG with cardinality constraint

Let $G=(V,E)$ be a vertex weighted DAG (Directed Acyclic Graph), with positive real valued weights. Let also $k\leq \left\vert X\right\vert$, is there any way to find the maximum weighted antichain ...
2
votes
1answer
44 views

Shortest path from that passes through a set of edges once

Given a graph with weighted edges. How to find the shortest path from vertex $A$ to vertex $B$ that passes through a set of edges $X$ at most once? $X$ can be big. Slow solution: Finding shortest ...
2
votes
1answer
43 views

Densely connected non overlapping subgraph

I'm trying to detect quasi cliques in an undirected graph. My problem is that I don't want any overlap between cluster. I'm currently trying to detect community using Louvain algorithm, but it ...
1
vote
2answers
32 views

What is the point of the “respect” requirement in cut property of minimum spanning tree?

The cut property stated in terms of Theorem 23.1 in Section 23.1 of CLRS (2nd edition) is as follows. Theorem 23.1 Let $G = (V, E)$ be a connected, undirected graph with a real-valued weight ...
0
votes
1answer
62 views

Voronoi Diagram: Exactly 2n-5 vertices

I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices. I tried to use the Euler ...
1
vote
1answer
32 views

Why does Skiena reserve space for n+1 adjacency lists?

I am reading up on graph theory from the book Algorithm Design Manual - Skiena. And he shows a structure of a graph as follows : ...
1
vote
0answers
42 views

Finding simple cycle of minimal weight in directed bipartite complete graph with negative cycles

Given a weighted complete bipartite directed graph K_{m,n}, is it possible to find a simple cycle (every node is visited at most a single time) with minimal weight in polynomial time (in m*n) when ...
0
votes
1answer
30 views

Understanding Jeff Erickson's analysis of a basic tree traversal algorithm

I have trying to understand graph algorithms from scratch and I have explored various resources but the most understandable for me was these lecture notes Algorithms. The way professor teaches seems ...
0
votes
1answer
40 views

An efficient algorithm to find a shortest cycle including a speciic vertex

We wish to find shortest cycle (if any cycle exists) that includes a special vertex $v$. We know if we run DFS on an undirected graph, back edges show us that there exists at least one cycle. This ...
0
votes
1answer
25 views

Longest path in DAG or finding DAG diameter

A directed acyclic graph (DAG), is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way ...
0
votes
1answer
19 views

choose minimum number of M professors in polynomial time in order to design all N course exams

Think that we have M professors and N courses every professor can wrote question for at least one course exam. we want to choose minimum number of professors in order to design question for all N ...
-1
votes
1answer
17 views

Program searching and visualising all simple paths between two vertices in undirected graph [closed]

I have undirected weighted labeled graph. What program i can use to generate and visualize tree graph, showing me all simple paths from vertice A to vertice B? //The vertices in each path should not ...
1
vote
0answers
39 views

Reducibility of finding Eulerian Path to Linear Programming

Consider any arbitrary directed, acyclic graph; how can we formulate the problem of finding a particular Eulerian path as a linear programming problem? It seems like there should be a relatively ...
1
vote
1answer
29 views

Minimum Weight Directed Subgraph ensuring all pairs reachability?

After some work on Minimum Spanning Trees and Steiner trees in combinatorial problems I came across this problem that I would like to look further in my research, but I want to know if there is an ...
0
votes
0answers
56 views

Misionnaries and cannibals problem (A* algorithm)

"In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if ...
-1
votes
0answers
24 views

The problem of graph coloring

Is there an algorithm that solves the problem of graph coloring in 3 colors with complexity $O(2^n · m)$?
1
vote
1answer
58 views

When to use DFS and when use BFS?

Preparing for an interview. I see two cases where each one is specially suited BFS: When you need to find shortest path between vertices (if one exists). DFS: If you need to find cycles in a ...
1
vote
0answers
21 views

What is the psuedo-code for Tremaux's Algorithm as a Depth First Search to solve a maze?

I was interested in the Tremaux Algorithm as a Depth First Search to solve a Maze. Unfortunately I was not able to understand what Data Structures are and how they could be used. For example, I saw a ...
3
votes
0answers
21 views

How to compute amortized complexity of n runs of Dijkstra's algorithm?

I'm trying to figure out how to compute an amortized complexity/ or complexity of this algorithm. We have a Graph which is oriented. And we are going to run Dijkstra's algorithm for finding a shortest ...
0
votes
0answers
28 views

Graph from dataset [closed]

I'm currently working on a project of my own and in order to continue i'd want to go from a dataset to a graph that represents some dependancy or correlation between the attributes.An example of the ...
1
vote
1answer
45 views

How do we generate a depth-first forest from the Depth First Search?

I was trying to implement an algorithm which finds the strongly connected components (SCC's) of a directed graph. In order to find the SCC's, as the last step we need to be able to generate the ...
1
vote
2answers
51 views

Equivalent definition of minimal spanning tree

Prove that $T$ is MST $\Leftrightarrow$ for any edge $uv \notin T$, $uv$ has the maximal weight on the cycle created by adding $uv$ to $T$. It's my attempt to prove $\Rightarrow$: Consider the ...
-2
votes
1answer
21 views

Connected Component in Graph

I am a bit confused about the notion of connected component of a graph. I understand what is a subgraph and what means for a graph to be connected. But the definition we got in class is this: "A ...
0
votes
1answer
27 views

What do we mean when we say an edge (u,v) connects some component to other component in forest G = (V,A)

Let H = (V,E) be a connected, undirected graph. Let A be a subset of E. Let C = (W , F) be a connected component (tree) in the forest G = (V,A). Let (u,v) be an edge connecting C to some other ...
0
votes
1answer
77 views

Complexity of the Dijkstra algorithm

I'm little confused by computing a time complexity for Dijkstra algorithm. It is said that the complexity is in $O(|V|^2)$ - Wikipedia - Dijkstra, which I ...
4
votes
0answers
37 views

MST that contains a shortest $s,t$-path

Consider the problem in which we have an (undirected) graph $G=(V,E)$, weight function $w:E\to\mathbb N$ and a pair of vertices $s,t\in V$, and are required to determine whether there exists an MST ...
4
votes
2answers
328 views

Why does Karger's algorithm work “with high probability”

I'm reading Karger 1993's "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm" (link). It states that a single round of contractions yields a min-cut with probability ...
0
votes
1answer
22 views

Longest path of a DAG containing a single node?

I'm interested in implementing an algorithm detailed on this Wiki page for finding the longest path of a DAG. The second part of the algorithm says the length of the longest path of a node with no ...
0
votes
0answers
36 views

How to find maxflow with minimum number of edges?

I am struggling with the flowing problem: You are given a source s and a sink t and a biparted graph G. All vertices {v} from the left half are connected to the source s with given capacity C[v]. ...
3
votes
0answers
26 views

Maximum set of equalities, subject to some inequalities

I have $n$ variables $x_1,\dots,x_n$. I'm given a set $E$ of equalities (each of the form $x_i=x_j$ for some $i,j$) and a set $I$ of inequalities (each of the form $x_i \ne x_j$ for some $i,j$). I ...
0
votes
0answers
36 views

How many more edges can be added to a graph while keeping it acyclic? [migrated]

If I have a connected, directed graph with n vertices and m edges, is there some sort of formula that describes how many more edges can be added to the graph while keeping it acyclic?
7
votes
2answers
109 views

What is the intuition on why the longest path problem does not have optimal substructure?

I was learning about longest paths and came across the fact that longest paths in general graphs is not solvable by dynamic programming because the problem lacked optimal substructure (which I think ...
1
vote
1answer
80 views

Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with $N$ vertices and $M$ edges. Each edge has its own weight and colour. There are at most 10 different colours in the whole graph. Each time I traverse edges of ...
3
votes
1answer
53 views

why should I go for logistic regression?

I am a student working on a Database management project with a bit of Python coding involved. The project is about Review Analysis.Basically I am trying to read a review and determine how good or bad ...
4
votes
0answers
105 views

Vertex Disjoint Path Covers of Hypercube-Like Graphs [migrated]

This is a followup question relating to an older question I posted, namely: Decomposing the n-cube into vertex-disjoint paths. Given a graph $G = (V, E)$ and sets of distinct vertices $S = \{s_1, ...
1
vote
1answer
20 views

Reconstruct the minimal path cost from the delta-stepping algorithm?

I was coding the delta-steppping algorithm from this paper. They describe almost everything about the algorithm but not how to get the path. As an output I am getting the dictionary tent where ...
0
votes
0answers
8 views

Should all internal node keys in B+ tree also be in the leaves?

I was reading about B+ tree insertion. The algorithm takes following form: Insert the new node as the leaf node. If the leaf node overflows, split the node and copy the middle element to the ...
2
votes
2answers
48 views

TSP problem with a benchmark data

I've got a test Travel Salesman Problem's data with known optimal solutions. It's in a form of set of 2D points. Particularly, this is a tsplib format; sources are here and here. I'd started a ...
1
vote
2answers
37 views

Is there a name for graphs which contain oriented and non-oriented edges?

Is there a name for graphs which contain oriented and non-oriented edges? I couldn't find on the internet if there exist a specific name for such graphs.