Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
1
vote
1answer
11 views
When is a root node an articulation point in a graph?
I am trying to find the articulation points in a connected undirected graph and I'm finding it difficult to figure out if the root node of the DFS is an articulation point.
Based on the literature I'...
0
votes
0answers
11 views
How could the Cuckoo Search be implemented into Python? (Presumably a solver) [on hold]
I was looking to do this for just a fun project, and maybe mine some GRIN coin.The proof-of-work for GRIN is the cuck(ar)oo29 algorithm, with 29 nodes in each graph. There is also an ASIC chain, for ...
1
vote
1answer
25 views
Minimum Spanning Tree with one particular edge minimised(continued)
I have recently encountered a coding problem, specifically, the CCC problem S4.
In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each ...
1
vote
2answers
36 views
Minimum spanning tree such that one edge can be minimised
During a computer coding exam, I have encountered such a problem.
Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the ...
0
votes
0answers
6 views
How to plot moving position of a particle with given time vector in matlab? [on hold]
I try to make an animation of plot in Matlab using vector $X$, vector $Y$ and given time vector $T$. There are several examples related to animation and plot with random time and with 'pause(t)'. It ...
4
votes
1answer
49 views
Find all edges in a tree whose removal doesn't separate color classes
Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$.
Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected.
...
1
vote
2answers
46 views
Does converting adjacency matrix representation of graph of size $n \times n$ to adjacency list always require $O(n^2)$ time?
Assume that I have the adjacency matrix representation of a graph in $0,1$ values. Does converting it to a corresponding adjacency list representation always have a time complexity of $O(n^2)$?
2
votes
1answer
31 views
Name of a tree with arbitrary number of branches at each fork point?
A binary tree is a rooted tree with the root having an indegree of 0 and all other nodes of 1. The outdegree is 0, 1 or 2 for all nodes.
How do you call a rooted tree if the number of branches per ...
0
votes
0answers
35 views
Generalized graph [on hold]
I have N (e.g. 10) attributed multigraphs like this:
They are similar, not same. And i need merge these 10 graphs into 1, which is general.
Use case is: I have one large multigraph, user marks 10 ...
0
votes
0answers
25 views
Number of ways to partition a tree(containing values in its nodes) into groups such that each group has xor sum equal to Z
I tried two approaches:
1. Give each edge two numbers on its left and right side denoting xor sum for subtree on its left and right respectively. If total xor sum for whole tree is Z, then it can only ...
1
vote
0answers
31 views
$n$ machines, $n$ types of jobs with $q_j$ jobs, minimizing the cost
I have this problem
A firm has $q_j$ jobs of type $j$, where $1 \leq j \leq n$. It also has $[n] = {1,2,...n}$ machines. Machine $i$ can service any job of type $j$ where $j ≤ i$. The cost of ...
0
votes
0answers
18 views
Did Menezes et al. switch the letters $\mu$ and $\lambda$ in Floyd's cycle detection note 3.8?
The letters $\mu$ and $\lambda$ are usually used to represent, respectively, the length of the tail of the graph and length of the cycle in the graph. But Menezes on note 3.8, page 91 (or PDF-page 6),...
0
votes
1answer
18 views
Sorting on non-linear topology
Disclaimer. What I'm going to ask about below may seem to be "Topological sorting". To my understanding, it is not. The latter runs in linear time, while I'm looking for a modification of the regular ...
1
vote
1answer
26 views
Path of maximum value with bounded cost in DAG
Consider a Directed Acyclic Graph in which every node has a value and a cost and edges do not have any weight. I need to find a path containing nodes such that sum of values of these nodes is ...
6
votes
0answers
105 views
Steps that guarantee exiting a maze
Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
0
votes
0answers
29 views
Contraction Hierarchies minimal distance proof
I am trying to implement "Contraction Hierarchies" algorithm and reading the white paper and watching video lectures [6,7]. But still I can't understand proof for the following lemma:
Lemma 1. $d(s,...
1
vote
1answer
40 views
Shortest path from source to all vertices, but with some wildcards
Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer).
You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated ...
4
votes
1answer
37 views
Maximum matching using linear programming
In a bipartite graph $G = (V,E)$, there is a neat algorithm for finding a maximum matching (or even a maximum-weight matching) using linear programming. It is explained here. The first step is to ...
0
votes
0answers
26 views
Algorithm for the following graph transformation
Given a directed graph $D = (V,A)$ with edge-weights $w\in\mathbb{R}_{++}^A$ I'm trying to construct the following graph $D'=(V',A')$:
For a fixed $v\in V$ we add a vertex $(v,0)$ to $V'$
For every $(...
1
vote
0answers
45 views
Finding the best state for chain graph with cycles
I have a chain graph like in the picture. Each node of the graph has finite possible labels, i.e. states, which define the node's weight(non-negative) as well as the internode weight(also non-negative)...
0
votes
0answers
28 views
topology representation through graph [closed]
Is there any way to represent indoor topology of a house through graphs or trees and calculate similarity or dissimilarity between them?
2
votes
1answer
39 views
List of algorithm problems in term of ideals
I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem ...
1
vote
1answer
26 views
Reduction Vertex cover into Dominating Set
I have a question to the reduction from Vertex Cover into Dominating Set.
So my lecture says if I have a undirected Graph $G = (V,E)$ where $S \subseteq V$ is a vertex cover. Then we construct a new ...
4
votes
2answers
73 views
Add lines to star with fixed coordinates maximizing smallest angle
I have the following problem:
There are existing stars (as in graph-theory stars) with a fixed representation in a 2D coordinate space, meaning that angles between the edges are not allowed to change....
1
vote
0answers
25 views
How do distributed algorithms for shortest path finding handle negative cycles?
I am searching the web for an answer to this question, but I have only found answers for non-distributed algorithms. I am interested in this for its application to Distance Vector routing.
-1
votes
1answer
29 views
Can someone point out why these directed graphs aren't equivalence relations?
As far as I can tell, these two directed graphs are reflexive, symmetric and transitive.
3
votes
1answer
56 views
Approximating the biggest acyclic subgraph of a given weighted digraph $G= (V,E)$
The base scenario is this: We're given a weighted, directed graph $G= (V,E)$, and are tasked to find an approximating algorithm which returns a digraph $G' = (V,E')$ (i.e. which only deletes edges) so ...
1
vote
0answers
17 views
Maximizing cache utilization when scheduling a computation graph
So I’m making a program where I generate a computation graph that will be executed on an external device, where the goal is to order the computations in the graph so that the whole computation is done ...
0
votes
1answer
32 views
Minimal edge cover of the hypergraph
We know that minimal edge cover for the normal graph is polynomial time solvable.
Is it also true for hypergraph?
1
vote
0answers
26 views
Proof that G is a Tree After DFS and BFS form the same tree T [closed]
Let G be a connected, undirected graph containing some vertex s. let's say that BFS and DFS are both run on G starting at s and that the breadth first search and depth
first search ...
2
votes
1answer
45 views
Djikstra algorithm analysis
My textbook says that the Dijkstra algorithm's runtime is $O(n) + O(m \log(n)) = O((n+m) \log(n))$. How did they come up with that?
Dijkstra algorithm pseudocode:
...
0
votes
1answer
24 views
set cover to edge cover
I want to find set cover of this problem.
I have sets, each of cardinality 3. I want to find set cover.
This is what I am doing.
Treat each set as an edge, which is incident on each of its element.
I ...
0
votes
0answers
8 views
Converting a cyclic digraph to an approximated tree
I have a digraph that represents a taxonomy of sorts, where nodes are "concepts" (i.e., person, animal, plant, etc) and the edges represent an is-a relationship. Hence, we can have ...
6
votes
1answer
117 views
Optimal partitioning of n-tuples
Motivation
Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into ...
4
votes
1answer
65 views
Topological sorting colored tree
EDIT: The most general case I need is not a tree but any Directed Acyclic Graph.
I have a directed acyclic graph.
I need to sort it in a list so that in the list every node comes after any node it ...
0
votes
1answer
21 views
minimum cardinality maximal matching of graph
How to find minimum cardinality maximal matching?
I tried that pick a edge from highest degree vertex remove other edges from same vertex and so on.
1
vote
1answer
50 views
Constructing a new graph. G'. What does it mean v ∈ S_{i+1}?
John lives in a city whose streets has the same length. His apartment is located at a specified node H. John need to do his errands where he visits each of k different shop in order. However, each ...
1
vote
1answer
43 views
Is there an algorithm to find the minimal number of dimensions, given the distances between points?
Given some finite set $S := \{x_1,x_2,\ldots,x_k\} \subset \mathbb R^n$ we can define a distance matrix $D = (d(i,j))_{ij}$ with $$d(i,j) = \Vert{x_i - x_j}\Vert$$
where $\Vert \cdot \Vert$ is the ...
1
vote
0answers
25 views
Searching Algorithm on Connected Graph
This is a recreational problem, not sure if it is asked due to my limited knowledge in discrete math.
Suppose we have a connected graph (which can be seen as a "map"). We start at an initial vertex, ...
1
vote
1answer
39 views
Partitioning vertices in a bipartite graph according to minimum vertex covers
How to solve this problem?
A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover ...
-1
votes
1answer
86 views
Algorithm : Visiting all stations in minimum time with additional constraints
I was given this question and not sure how to solve this. This is a DP minimization problem ?
Problem :
There are N stations in a certain region, numbered 1 through N.
It takes di,j minutes to ...
0
votes
0answers
18 views
Finding subgraph in multigraph using deeplearning
I have big multigraph each node represent entity with 0..n attributes(e.g. name, address, salary). My problem is: I will get for example 10 subgraph selected from user and these subgraphs represent ...
1
vote
0answers
23 views
Calculating maximum number of splits that can occur during insertion of $n$ keys in B Tree of order $m$
I can calculate this by trying out manually inserting $n$ keys in $m$ order B Tree as follows:
Assume median to be selected for split be left biased. That is $m/2$. For example, if $m=4$, then a ...
0
votes
0answers
36 views
The computational cost of the adjacency-based Euclidean distance matrix
I know that the computational cost of the adjacency matrix is n*n. Namely, this graph-theoretical structure contains value 0 or 1 for every pair of vertices if there the edge exists or not, so it ...
1
vote
0answers
19 views
Maximum subset of connected edges
I have a graph $G$ with $m$ vertices $V$ and $n$ edges $E$. $G$ is weighted, directed, and cyclic. I want to select heaviest $k$ edges from $E$ such that all of the edges form a connected, undirected ...
0
votes
0answers
37 views
Modifying BFS to Find the least transfer stop as possible
let's say that a map of a bus system is provide by as graph G. and each edge of this graph is colored to distinguish which of bus lines that edge is associated with. Come up an algorithm which ...
0
votes
2answers
31 views
Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal
In CLRS, in the later part of breadth first search topic, for unweighted graphs, it says:
At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable ...
1
vote
1answer
22 views
Number of min-cuts of a graph
It can be shown that every graph G has at most $\binom{n}{2}$ min-cuts.
It follows from Karger’s algorithm Analysis.
Is there a different combinatorial proof of this fact? Was this known before ...
2
votes
1answer
61 views
Longest-path in a graph, where the path should be 'straight'
Is there any existing work done on finding paths that are geometrically straight?
I encountered a problem where I'd need to find the longest straight(-ish) path in a web of connected nodes, each of ...
3
votes
1answer
65 views
Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue
we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete_min, O(log |V |) for insert/ decrease_key, so the overall run time is O((|V|+|E|)log|V|).
Now let's modify ...
