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.

0
votes
1answer
10 views

Simple algorithm to generate a linear extension from partial order set

I usually do it via topological sort and wonder if there is a simpler way to generate a linear extension from partial orders without consider the graph of the relation.
2
votes
1answer
26 views

All pair shortest path in a tripartite graph

I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination ...
2
votes
2answers
76 views

Negative simple path NP-Complete

Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$ My approach was to ...
2
votes
1answer
435 views

Approximating maximal independent set with a minimal vertex cover approximation

The minimal vertex cover problem has a 2-approximation algorithm. We can reduce the maximal independent set problem to the minimal vertex cover problem as shown here. Does this mean that I can use ...
3
votes
2answers
242 views

is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

I'm working on exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition): A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ implies that $G$ contains at ...
3
votes
0answers
27 views

What is the current fastest algorithm for finding the maximum common subgraph?

First of all, it's my first time in #ComputerScience at StackExchange so, my apologies if I'm making some newbie mistake when asking this question. So, I'm currently researching algorithms for ...
-1
votes
0answers
19 views

Formula for maximum matching in bipartite graph

Let $G = (U, W, E)$ be a bipartite graph. Show that $\alpha'(G) = \min(|U| - |S| + |N(S)|)$, where $S$ ranges over all subsets of $U$, $\alpha'(G$) is the size of maximum matching of $G$, and $N(S)$ ...
-1
votes
0answers
13 views

Find paths between 2 vertices in a Graph

which algorithm can be used to find the paths between two vertices of an unweighted graph ? I tried to use BFS and DFS to solve this exercise but I'm not sure it could help me complete it.
3
votes
1answer
49 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 ...
0
votes
0answers
26 views

Simplification of an objective function of an optimization problem [on hold]

Let $G(V,E)$ be an undirected weighted simple graph, where $V$ and $E$ are the set of vertices and edges. Let $A \in \{0,1\}^{n\times n}$ and $W \in R_+^{n\times n}$ be the adjacency matrix and the ...
1
vote
3answers
790 views

Connected components of the graph on $[n]$ in which $i,j$ are connected if $\mathrm{gcd}(i,j) > g$

I recently got asked the following question: A set of $n$ cities are numbered from 1 to $n$. Given a positive integer $g$, two cities are connected if their greatest common divisor is greater than $...
1
vote
1answer
39 views

Find path from node 1 to N with lowest possible max cost

I have an assignment where I need to find a path from node 1 to node N in an undirected graph given weights in O(E Log^2 E) and using a ...
1
vote
1answer
16 views

Graph partitioning with parts of equal size

Partition an undirected graph of $n$ nodes into $k$ subgraphs so that total vertices inside all subgraphs is maximum. Restriction: all subgraphs have the same number of nodes (so $k$ divides $n$);...
0
votes
1answer
19 views

Dijkstra complexity analysis using adjacency list and priority queue?

I just got to look at the Implementation of Dijkstra using adjacency list and priority queue. The time complexity is $O(E\log V +V)$, I tried looking for the proof but couldn't find one. Any help will ...
2
votes
2answers
480 views

Easy instances of the coloring problem on graphs with degree at most 4

Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color. In ...
0
votes
0answers
28 views

Clique number of a graph given its order and average degree

Let $G$ be simple graph of order $N$, and let $\bar{d}$ be its average degree. Find the maximum value of $\omega(G)$ (the clique number of $G$) as a function of $N$ and $\bar{d}$. Find the ...
3
votes
1answer
38 views

Proving NP hardness about graph creation problem with triangle number

I have graph creation problem. Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in ...
1
vote
1answer
56 views

Word ladder problem for words with different length

Is there some one who know any algorithm for word ladder problem with words of different length? Actually we have some strings with same length and some strings with one length longer but not from ...
1
vote
1answer
14 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) [closed]

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
27 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
40 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 ...
4
votes
1answer
52 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. ...
0
votes
0answers
6 views

How to plot moving position of a particle with given time vector in matlab? [closed]

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 ...
1
vote
2answers
48 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)$?
0
votes
0answers
36 views

Generalized graph [closed]

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 ...
2
votes
1answer
32 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
votes
2answers
29 views

calculation of Transitive Closure

This question is not from homework, but rather as preparation for the test: The calculation of place-in is a calculation in which the algorithm does not need space beyond the output size (beyond ...
25
votes
7answers
36k views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
0
votes
0answers
27 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
32 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
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 ...
0
votes
0answers
19 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
21 views

Removing max number of edges while keeping minimum distances

Suppose we have a graph with vertices from 1 to n.The graph is undirected and the starting point is 1 and we have path from 1 to any other vertex.We also have positive weight on each edge and there ...
8
votes
0answers
129 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 ...
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 ...
0
votes
2answers
52 views

Quick and space-efficient way to find whether two sets intersect

I hope you can help me - Given a lot of sets containing integers, I'd like for any two sets, to quickly (i.e. O(1)) ask whether they intersect. Note that I don'...
2
votes
1answer
30 views

How to find how many times an object's path crosses another?

I have several hundred objects that will move in a fixed area throughout the day. Frequently the objects will cross over another object's path, either at the same time (eg. a collision) or within a ...
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
41 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
40 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 ...
3
votes
1answer
59 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 ...
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)...
1
vote
3answers
986 views

Kosaraju's Algorithm-Strongly connected components

In Kosaraju's Algorithm, using first dfs (traversing on reverse graph) we calculate finishing time of nodes, and then traverse (actual graph) in reverse order of finishing times. why not without ...
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
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.
4
votes
2answers
75 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
1answer
28 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 ...
-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.