Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

Filter by
Sorted by
Tagged with
-1
votes
0answers
10 views

what happens to max flow if we decrease the capacity of every edge by some constant?

Given a graph $G = (V,A)$, with source $s$, sink $t$, edge capacity larger than 1 (but not all equal), I know that if we decrease the capacity of one edge by 1, the $s,t$-maximum flow decreases by at ...
-1
votes
0answers
16 views

Finding vertex coverage that is also independent set

Given a graph G and integer k, find a vertex coverage set of size k that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea ? ...
1
vote
2answers
152 views

Removing vertices from a labelled graph

Let $G$ be an undirected graph with each vertex labeled with an integer. Is there an algorithm to remove a subset of vertices such that in the resulting graph with deleted vertices no vertices with ...
0
votes
1answer
33 views

Network Flow - Minimum flow in a network

I have a directed graph G=(V,E) with a source s$\in V$ and a sink t$\in V$. There is a minimum capacity (lower bound) l $_{e}$ for each edge in G. There are no upper bounds on the edges. In a course ...
0
votes
2answers
40 views

Shortest path from $s$ to $v$ in unweighted simple directed graphs

Let $G=(V,E)$ be an unweighted simple directed graph. Some of the edges are colored red. Let $E'⊆E$ denote the set of red edges. Given a vertex $s∈V$,suggest an efficient algorithm for finding the ...
1
vote
0answers
25 views

How to check whether given $k$ vertices make a $k$-clique in an undirected graph $G$ efficiently

Let $G=(V, E)$ be an undirected graph with vertex set $V$ and edge set $E$. Let $V'=\{v_1, v_2, ..., v_k\}$ be a subset of $V$ where degree of each $v_i$ is bigger than or equal to $k$. Is there a way ...
0
votes
1answer
25 views

Which Graph Algorithm should I use to find all possible groups in a graph?

I have the following situation: (Alex, Bob) (Alex, Charlie) (Debra, Erika) Imagine that each row in the list represents a friendship. Alex is friends with Bob. Alex is friends with Charlie. And ...
2
votes
0answers
48 views

Given undirected and connected graph G=(V,E). Prove for any DFS run: for any u,v∈V if u.d>v.d then u.d−v.d≥δ(u,v)

Given undirected and connected graph $G = (V,E)$. Prove for any DFS run: for any $u,v \in V$ if $u.d>v.d$ then $u.d − v.d ≥ δ(u,v)$ $δ(u,v)$-distance of a shortest path (not necessarily unique) in ...
1
vote
3answers
53 views

What's the best algorithm to find the shortest path between 2 vertices in a graph?

Considering an undirected and unweighted graph, what's the best algorithm to find the shortest path between two vertices?
-1
votes
0answers
16 views

I want to create an unsigned 8-bit adder/substractor and implement it in a logic circuit [closed]

I am having a hard time trying to implement an adder for 8-bits unsigned numbers with 1's complement but without using VHDL since I am new to this kind of stuff. But I know that I should use 8 full ...
-1
votes
0answers
11 views
1
vote
1answer
22 views

Prove G have a single MSP

We have undirected connective, weighted graph $G = (V,E)$. we also know that for every $e,e'$ in $E$, $w(e)≠w(e')$. Prove that $G$ has a single MSP. Ideas?
1
vote
0answers
16 views

Practice question on the applications of flows and cuts

This question is from Erickson's textbook on algorithms, p. 376, question 18. Faced with the threat of brutally severe budget cuts, Potemkin University has decided to hire actors to sit in ...
0
votes
0answers
28 views

Weight of minimum spanning tree of G and T

We have undirected weighted connective graph $G=(V,E)$, We also have a minimum spanning tree $T$ of $G$. Let $v$ be some vertex. We have new graphs, $G'$ and $T'$. $G'$ and $T'$ are same $G$ and $T$, ...
0
votes
0answers
26 views

Divide Minimum Spanning Tree into Equal (Disconnected) Chunks [closed]

Does anybody know an efficient algorithm for dividing Minimum Spanning Tree (MST) into equal in size disconnected sub-trees? I'm not saying that it is a particularly hard task, but maybe there exist ...
0
votes
1answer
103 views

Inviting an optimal subset of persons such that all friends of a person invited are invited

Let's say that you want to invite a person $u$ in party $P$. The person $u$ will join the party if and only if all the friends of $u$ will join the party as well. Otherwise, $u$ will reject your ...
1
vote
1answer
27 views

How Tarjan algorithm work for the 2-SAT

Tarjan's algorithm for 2-SAT is based on the truth: a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation. But I ...
0
votes
0answers
19 views

Creating capacity graph for a list of flights?

I have a list of flights and for each flight, I have information like source, destination, flight capacity, arrival time, departure time. There are only 8 distinct values that are populated in the ...
0
votes
0answers
15 views

Decomposition of graph to subgraphs according to parallel edges

I am supposed to calculate all-pair shortest path lengths of a graph. However, I first need the graph to be decomposed/expanded to a simple one based on the presence of parallel edges. If N parallel ...
3
votes
1answer
41 views

Maximum value of arbitrage

I'm trying to solve this from The Algorithm Design Manual: 6-23. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time ...
2
votes
1answer
38 views

Proving that max flows of undirected graph and equivalent directed graph are equal

There is an undirected graph $G$. A graph $H$ is constructed by changing each edge $(a,b)$ in $G$ to a pair of directed edges $(a,b)$ and $(b,a)$. How to prove that the maximum flow in $H$ is equal to ...
3
votes
1answer
21 views

Graph of size n with girth >2k and minimum degree more than n^1/k

I'm stuck at a proof about Graphs in the context of Graph Spanners. A Lemma says: Let $G$ be a graph with $n$ vertices and $m$ edges. If $G$ has girth more than $2k$, then $m\leq n^{1+\frac{1}{k}}$. ...
-1
votes
2answers
64 views

Enumerate all paths of length 3 in a given tree T

Kind help with an algorithm or any refrence to enumerate all paths of length 3 in a given tree T in the shortest possible time.
0
votes
0answers
28 views

A heuristic for finding an edge cycle cover

I am looking to find a minimum list of cycles in a graph such that their union gives the list of all simple cycles in this graph. In the example below, here are 4 simple undirected cycles: 1-2-3, 2-3-...
3
votes
3answers
131 views

How to find a path that connects all the dots in the matrix?

I have a matrix that consists of 0, 1, 2. 0 - dot. 1 - block. 2 - start dot (initial position in the path). I have to create a path from the start dot, that connects all the dots in the matrix and ...
0
votes
0answers
17 views

Counting nodes within K distance from set of given nodes in a tree [duplicate]

I was going through this article https://www.geeksforgeeks.org/count-nodes-within-k-distance-from-all-nodes-in-a-set/ The question says: Given an undirected tree with some marked nodes and a positive ...
1
vote
0answers
18 views

Scapegoat Trees: Why are they only loosely a-height-balanced?

From Wikipedia: Even a degenerate tree (linked list) satisfies this condition if α=1, whereas an α=0.5 would only match almost complete binary trees. A binary search tree that is α-weight-...
5
votes
2answers
71 views

Modifying digraph to make it strongly connected

I came across this problem and have not been able to find a solution. Given directed graph $G$, devise an algorithm to find the minimum number of edges to flip/change/transplant such that the ...
0
votes
0answers
24 views

You're walking in a maze,you must visit all reachable squares of distance k. The performance of the algorithm is measured by the total distance walked

The maze is a 2D Grid of known width and height. it's composed of squares: a Wall or a room. You cannot walk into walls. from each room you can only get to adjacent rooms. ( you can't teleport) You ...
1
vote
1answer
63 views

How to find maximum matching edges in undirected tree

Let $B$ be an undirected tree with $|V|$ nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime $\mathcal{O}(|V|)$. My approach: ...
3
votes
1answer
35 views

Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?

So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time ...
1
vote
1answer
31 views

Shortest paths from a source in weighted graph with only one negative weighted edge

Of course assuming there aren't any negative cycles. I saw this question somewhere. And i saw a complicated solution which says to build three such graphs and connect between them in a very ...
1
vote
0answers
33 views

How to build a set of closed chains with a sequence of different vertices?

I have a set of many bi-directional links like A-B, A-C, B-C, A-D, C-D, D-E, etc. I need to find a set of many closed chains with a sequence of different vertices (...
3
votes
0answers
46 views

Number of maximal cliques in a graph where the largest induced cycle is $C_4$

So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices. In general, it is exponential. I am trying to determine whether the number ...
1
vote
0answers
16 views

Showing that a directed graph that has a cycle belongs to NL [closed]

DCG = { G | Directed graphs that contains a cycle } How can I proof that DCG belongs to NL?
1
vote
1answer
24 views

Intuition behind min cut in a flow network? Whether it's baseball elimination or project selection

I was wondering if someone can give me a general definition of a min-cut besides it being the max flow of a network. For example, in the baseball elimination problem, if we wanted to find out if ...
2
votes
2answers
84 views

Prove or disprove - graph doesn't exists

So, we have a directed graph G whose basis graph is connective. I was asked to prove or disprove If its possible that for every DFS run on G, the output will be two trees containing all G vertices . ...
1
vote
1answer
25 views

Special case of the $MST-$ Problem

I am working on the following exercise: Consider an undirected complete graph $G(V,E)$ and positive real numbers $a_1,a_2,\ldots,a_n$. The task is to find a MST with respect to the edge weights $...
1
vote
1answer
39 views

Determine shortest path in a 4x5 grid graph

Suppose we had a graph $G = (V,E)$. This graph can also be seen as a $4x5$ grid graph as shown in the image. There is a directed edge from $v_{i,j} \rightarrow v_{i,j+1}$ for $1 \leq i \leq n$ and ...
1
vote
0answers
18 views

For what family of graphs does Dijkstra's algorithm achieve the run-time upper bound

The question is in the title of the post. I am hoping to get some validation regarding my solution. After some trial and error, my idea is as follows. Worst case complexity of $\mathcal{O}(E\lg_{}{V}...
4
votes
1answer
40 views

Computing a pre-topological sort using a BFS/a queue

Computing a topological sort in a DAG using a queue simply amounts to putting the nodes with indegree 0 in a queue, and going through the queue removing these nodes from the graph and adding the nodes ...
1
vote
0answers
14 views

Whic representation of graph is preferred, anjacency matix or adjacency list? [closed]

I have a graph in which vertices are 100 and edges are more than 300. If I want to represent this graph in either adjacency matrix or adjacency list, which graph representation will be preferred? My ...
1
vote
1answer
36 views

Doubt on Karger's Algorithm for Min-Cuts

I am learning Karger's algorithm for Min-Cuts.I have been solving 1 problem on it. The first part of the problem asks us to run Karger's Algorithm on a given graph. I have no problem doing that. My ...
1
vote
1answer
25 views

Finding stages in routing algorithm

I have an undirected graph where I need to find routes of minimum cost in a point to multi-point, but where cost can be reduced by creating intermediate "packs" of routing terminals. I am currently ...
2
votes
1answer
27 views

Number of spanning trees in undirected simple graph

What is the number of spanning trees in an undirected simple graph? My attempt: Let $m$ be the number of edges in a simple graph, and let $n$ be the number of vertices. Then number of spanning ...
4
votes
1answer
44 views

Optimal root in shortest path tree (SPT)

I would like to find the "optimal" shortest path tree (SPT) in some undirected weighted graph. As "optimal" SPT, I mean so its maximal path from root to leaf is minimal from any other potential SPTs. ...
0
votes
1answer
30 views

find total components in a graph

I have a graph with N nodes and M edges. It is a single component. Now I have to delete a single node from graph, deleting that node might split graph into 1,2 or more components. The count of such ...
2
votes
1answer
59 views

Add edges to undirected graph to make connected and minimize longest path

I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the ...
0
votes
1answer
21 views

degree distribution

Does anyone know how to compute node degree distribution in a graph ? I am talking about a large graph for example California road network and imagine we have some data such as number of nodes and ...
0
votes
0answers
16 views

How to divide services and capacities in a graph?

Given a graph where some nodes can provide some services with x,y,z... capacities. A node connected to multiple nodes needs to divide these services to the connected nodes and these nodes themselves ...