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
1answer
13 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
votes
0answers
15 views

Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with N veritces and M edges. Each edge has its weight and colour. There are at most 10 different colours in the whole graph. Each time I pass edges of different ...
3
votes
0answers
36 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 ...
2
votes
0answers
22 views

Vertex Disjoint Path Covers of Hypercube-Like Graphs

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, ...
-3
votes
0answers
20 views

Can one use BFS to obtain a MST for a weighted undirected graph?

Can one use BFS to obtain a MST for a weighted undirected graph ?
1
vote
1answer
18 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
6 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
1answer
20 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.
1
vote
3answers
58 views

Travelling salesman very rough min and max estimates

Is there a way to find very rough minimum and maximum estimates for the travelling salesman problem? The estimates only need to be within the roughly same magnitude, but it's important that the ...
-1
votes
1answer
22 views

Maximum flow with Edmonds–Karp algorithm

I am learning Edmonds–Karp algorithm , I formed following flow network, (capacity is described above arrow, where s is source and t is sink.) If we first follow path S - A - C - T , we will get ...
2
votes
0answers
58 views

Finding all cycles of length <=5 in a directed graph?

I was wondering if there's an efficient way to find all cycles of a graph of length <= 5 in a directed graph. I've read up on Johnson's algorithm that takes ...
1
vote
1answer
23 views

Efficient algorithm for finding weakly connected components

We recently studied Tarjan's algorithm at school, which finds all strongly connected components of a given graph. I was curious however how one would find all weakly connected components (I had to ...
1
vote
1answer
42 views

Algorithm to find a path connecting given nodes in a graph

Suppose I have $n$ nodes in a graph and I identify $x$ nodes in the graph (where $x < n$). I would like to find a path to connect all those $x$ nodes I have identified. Is there any algorithm for ...
0
votes
1answer
28 views

Facts about internal and external path lengths of binary tree

While learning binary tree's properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search. My book specifies some ...
1
vote
1answer
36 views

What does a ball of center v and radius r with at most r hops away mean?

I am trying to understand what that sentence means. Intuitively, its obvious a radius ball means in a $ \mathbb{R}^{n}$ with respect to some norm. Its just the following set: $$ B(v, r) = \{ x \in ...
0
votes
0answers
39 views

Simple Way to Convert an Adjacency Matrix to a CSR Graph and Vice Versa

Let's say for the following weighted, undirected graph: I am given the adjacency matrix A[5][5]: ...
0
votes
1answer
18 views

What are positive and negative circles in weighted digraph?

I am going through Warshall and Floyd algorithms and I read that Floyd's algorithm does not hold if a graph has negative circle. I have not been able to fully figure out what negative circle means. ...
0
votes
1answer
37 views

Why does Dijkstra's algorithm not account for updating node distances after expanding a node?

Why does Dijkstra's algorithm not re-evaluate/re-expand nodes who have been expanded and later had their weight changed? For example, in the accepted answer of this question (link), if the algorithm ...
0
votes
1answer
21 views

Would incrementing the min cut edges by 1 increase the max flow by 1 as well?

Given the theorem that max flow <= min cut, Would incrementing the min cut edges by 1 increase the max flow by 1 as well?
-1
votes
1answer
44 views

How to Convert a Directed Graph to an Undirected Graph (Adjacency Matrix)

Given an adjacency matrix, what is an algorithm/pseudo-code to convert a directed graph to an undirected graph without adding additional vertices (does not have to be reversable)? similar question ...
5
votes
1answer
65 views

A* graph search time-complexity

Some confusion about time-complexity and A*. According to A* Wiki the time-complexity is exponential in the depth of the solution (shortest path): The time complexity of A* depends on the ...
2
votes
1answer
53 views
+100

Find all non-isomorphic graphs with a particular degree sequence

I have a degree sequence and I want to generate all non-isomorphic graphs with that degree sequence, as fast as possible. The only way I found is generating the first graph using the Havel-Hakimi ...
0
votes
0answers
40 views

Find closed loops in an undirected graph given an adjacency list

I am trying to find all the cycles in an undirected graph given the adjacency list of the vertices, with the an output of all the cycles in form of the vertices they are made up of. For example ...
0
votes
1answer
14 views

Push relabel why return back to source

In push relabel algorithm, at the end excess at any nodes is pushed back to source by raising height of those nodes above the height of source. Why is this done? In CLRS it's mentioned: To make ...
1
vote
1answer
45 views

Partial path known in Single source shortest path problem

I'm using the A* algorithm with a consistent heuristic on a graph to determine the shortest path. If the algorithm is exploring a node $p_1$ for which there is a existing knowledge about the optimal ...
0
votes
1answer
18 views

Check Cycles- On adding an edge in DAG

Given a DAG N, if an edge $(U \rightarrow V)$ is added between any existing nodes U and V. Then, by performing DFS from the node $U$ and checking whether there is a cycle or a not, should be ...
-1
votes
3answers
89 views

Terminology for trees

In a tree, I want to refer to a particular child of a node, the child of this child, the child of this child of this child, and then the child of this child of this child of this child. For instance, ...
3
votes
0answers
48 views

Tree of Despair: Collecting Data from a Tree with Multiple Types of Branching

Provided is a tree with three types of node. The structure of the tree cannot be modified and traversal of the tree is limited to querying a node for its children or its parent. The objective of the ...
3
votes
1answer
26 views

Why can't we run Bellman Ford from the source and relax edges out from the neighbours recursively and do a single pass through the edges?

At each $k$ th iteration of BF, we can are guaranteed to have computed the shortest paths that are at most $k$ long. That makes perfect sense me. If we relax a set of edges $k$ times, then we for sure ...
2
votes
0answers
32 views

Minimum cost edge disjoint paths - NP hard?

I've been stuck on this problem for a while now. Here it is: The Network Reliability Problem (NRP) is defined as follows: Given an undirected graph with $n$ vertices $v_{1}, \dots, v_{n}$, a ...
1
vote
1answer
23 views

Can minimum or maximum height of the binary search tree be constrained by the position of some elements

I came across one problem, which read as follows: We want to place the 13 letters A, B, C, D, E, F, G, H, I, J, K, L, M in a binary search tree with the minimum number of levels: 4. Because there ...
-3
votes
1answer
28 views

Shortest path with no two consecutive edges from a certain edge set

Given a graph with nodes $N$ and two sets of edges $E_1$, $E_2$ where no two edges from $E_2$ can be used consecutively, find the shortest path between $n_1, n_2 \in N$. Is there a smart way to ...
0
votes
0answers
28 views

Rank graph edges by importance

I have a graph data structure that represents a rail network. The nodes of the network are the train stations and the edges are the connections between stations. Running PageRank on this graph gives ...
2
votes
0answers
23 views

Maximum Weight Planarization of Size $n$ [duplicate]

Problem: Maximum Weight Planarization Given a weighted non-planar graph with $n$ vertices, and $m = \mathcal O\left(n^2\right)$ edges. Find the subgraph with $n$ nodes (but possibly removing edges ...
5
votes
0answers
34 views

Coercing a list of nodes into the most probable tree

Suppose that we have an RTF document which contains sections and sub-sections. The sections and subsections all have headings that are visually marked up (e.g., bold and italic), but the document ...
0
votes
0answers
26 views

Capacitated min-k-cut problem

In the capacitated min-$k$-cut problem we are given a graph (hypergraph) with non-negative edge (hyperedge) weights. The task is then to find a partitioning of the graph's vertices into $k$ sets of ...
3
votes
0answers
53 views

Context-free grammar for DAGs?

I'm looking for a "safe" representation of DAGs. With "safe" representation I mean that it can be described by a context-free grammar. Ideally, this grammar would be suitable for a simple LR parser. ...
0
votes
1answer
29 views

Log reduce PATH to DISTANCE-PATH

An instance of PATH is given by where G is a directed graph, s and t are nodes in the graph, it's a true instance if G has a path from s to t. DISTANCE-PATH is similar, but with an extra requirement ...
2
votes
0answers
41 views

Kleinberg Rubinfeld Short Paths in Expander Graphs for Hypergraphs [migrated]

In 96 Kleinberg and Rubinfeld in "short paths in expander graphs" showed that for any $\Delta$-regular $\alpha$-expander graph ($\alpha >0$) $G$ on $n$ nodes, if $H$ is any graph on at most $cn/ ...
3
votes
2answers
98 views

Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?

I just wrote a program that runs the Travelling Salesman Problem using the Nearest Neighbor Algorithm. Afterwards, I started looking into Minimum Spanning Trees (MST). From my understanding: The ...
0
votes
0answers
16 views

Linear and Non-linear data set in K-means algorithm

The site K-means says that the algorithm fails for a non-linear data set. What do you mean by a non-linear data set in clustering algorithms? How different is it from a linear-data set?
5
votes
1answer
53 views

How to detect intersecting segments based on length of the segments

As part of a larger problem, I am trying to detect based on the distance matrix which segments intersect in the original 2D space that originated the matrix. I don´t have coordinates (lat/long, x/y or ...
12
votes
4answers
336 views

Dijkstra's algorithm on huge graphs

I am very familiar with Dijkstra and I have a specific question about the algorithm. If I have a huge graph, for example 3.5 billion nodes (all OpenStreetMap data) then I clearly wouldn't be able to ...
-3
votes
1answer
47 views

Finding the minimum sum path between two vertices in an undirected weighted graph

What algorithm would I use for finding the minimum-weight path between two vertices in an undirected weighted graph? Dijkstra is for shortest path, but I need path with the minimum sum of the ...
2
votes
1answer
21 views

finding shortest negative cycle

Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the shortest (uses the least number of edges) negative weight cycle in the graph? I know that I can ...
4
votes
1answer
33 views

Finding the lowest-weight negative cycle in a weighted digraph

Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the negative cycle in the graph whose weight is as small as possible? I know that I can detect ...
3
votes
1answer
57 views

Articulation Vertex, significance and real world usage?

This question is not about any particular algorithm to look for articulation vertices (cut vertices) in a graph but rather seeking real world applications of algorithms involving such vertices. I am ...
1
vote
0answers
21 views

Difference between graph-partitioning and graph-coarsening

What is the difference between graph-partitioning and graph-coarsening with respect to scale-free networks? I am trying to analyze graphs generated using the data from social networks. Do both the ...
3
votes
1answer
24 views

Should planar Euclidean graphs be planar straight-line graphs?

An Euclidean graph, by definition is A weighted graph in which the weights are equal to the Euclidean lengths of the edges in a specified embedding and a graph is called planar if it can ...