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.

1
vote
1answer
32 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
51 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 ...
5
votes
1answer
61 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
91 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
36 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 ...
1
vote
0answers
34 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
23 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
32 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 ...
12
votes
0answers
227 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
31 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
57 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
78 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
46 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)...
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
37 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
82 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
30 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
103 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
20 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
34 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
58 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
49 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
42 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
125 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
85 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
51 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
53 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
54 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
31 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
100 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
139 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
20 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
34 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
46 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
23 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
42 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
124 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
28 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
70 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
73 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 ...
3
votes
3answers
77 views

MST: Is there such an example of a graph with unique mst and not unique light edge?

The problem is the following: Give an example of a graph that has a unique minimum spanning tree but for every cut of the graph, there is not a unique light edge crossing the cut. I am trying to ...
2
votes
0answers
18 views

Reducible from vertex cover for only some inputs

Suppose I have an NP problem, $\text{PROBLEM}(n)$, such that for certain values of $n$ I can get a reduction from vertex cover with $n$ vertices, and for others such a reduction is not possible (if $\...
0
votes
0answers
40 views

Finding all edges on any shortest path between two nodes using dijkstra

Given a directed weighted graph, we need to mark all edges (represented by an ordered triple of (source,destination,weight) ) which lie on some shortest path from source to destination (there could be ...
1
vote
1answer
37 views

Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached

Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached. I thought to run an SCC algorithm to find binding ...
4
votes
1answer
100 views

Finding a subset with few neighbors

Given a bipartite graph $G(X+Y,E)$, how can I find a non-empty subset $Y'\subseteq Y$, such that $|N(Y')| \leq |Y'|$ (where $N$ is the set of neighbors)? If $|Y|\geq |X|$ then the problem is easy - $...
3
votes
1answer
59 views

Intersection of two shortest paths in connected weighted graph

Let $G=(V,E)$ be a connected directed weighted graph with non-negative weights on edges. Let $u,v,s,t$ be vertices in the graph $G$. I need to find an algorithm which in $O(|E|\log |V|)$ time checks ...