Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
0
votes
0answers
15 views
Can ideas of maximum flow be used to solve the problem of traffic?
So I'm considering the problem of traffic congestion. I was wondering if it is possible to solve the problem of Maximum Flow on a graph representing a city, at least in theory (lets say you have ...
0
votes
1answer
29 views
MST Of An Almost Tree
A graph $G = (V,E)$ is called an almost tree if it is connected and has most $n + c$ edges where $n = |V|$ and $c$ is a small constant number. How would I go about designing an algorithm for a given ...
0
votes
0answers
18 views
BFS better performence
I got the undirected unweighted graph. Where every node represents one city. Every city produces one type of grocery (does not have to be unique).
Then you will have on the input a number of type ...
0
votes
0answers
22 views
How to randomly sample a social graph to find paths between at least 20% of profiles?
Given a Graph, where we know
Total number of nodes (~100,000)
Average no of connections per node (~200)
Maximum distance between two nodes (~5)
How many nodes (and its connections) do we have to ...
0
votes
0answers
11 views
0
votes
0answers
3 views
Network Connectivity lifetime or duration between two mobile nodes
I have created two mobile nodes m1 and m2 in NS-3 Simulator for 1000 seconds.
I need to calculate the network connectivity lifetime or duration for these two mobile nodes with the following ...
1
vote
2answers
33 views
Given a sorted dictionary of words, find order of precedence of letters
This question is found at: https://www.geeksforgeeks.org/given-sorted-dictionary-find-precedence-characters/
Given a sorted dictionary (array of words) of an alien language, find order of characters ...
1
vote
1answer
37 views
Is every graph with minimum degree $n/2$ connected?
Claim: Let $G$ be a graph on $n$ nodes, where $n$ is an even number. If every node of $G$ has degree at least $n/2$, then $G$ is connected.
Decide whether the above claim is true or false, and ...
0
votes
0answers
15 views
Starting point for converting recursive graph algorithms into the distributed MapReduce computation model
I would like someone to point out a few starting points and give some advice, so that I convert some algorithms that do clustering and community detection in probabilistic graphs and described in a ...
0
votes
0answers
13 views
Can we update a cut-block tree in linear-time?
Every graph $G$ admits a cut-block-forest decomposition. This is a forest $F$ where each node corresponds to a maximal 2-connected component (called block) in $G$ and two nodes are adjacent in $F$ if ...
0
votes
1answer
29 views
Visit all vertices of a graph
I need to find the fastest route passing in all vertices
Each vertex is a class.
I can choose the number of classes for semester.
Some classes have prerequisites (A and B need to be done one semester ...
0
votes
1answer
59 views
Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?
Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number ...
1
vote
0answers
32 views
Minimum and maximum of sum of inverse degree of a graph
Suppose we have a simple undirected graph $G(V,E)$, where $V$ and $E$ are the set of vertices and edges respectively. we denote $d(v)$ as the degree of a vertex $v \in V$. I am interested to find ...
4
votes
1answer
56 views
Given a directed graph, allowed to reverse one or zero edges to make shortest path from S to T
I googled and couldn't find something similar, thanks for your attention and help.
EDIT:
Thanks for your feedback. Now I try to be more clear.
Given a directed graph with $V$ vertices and $E$ edges....
-2
votes
1answer
36 views
algorithm to generate partition graph [closed]
Given a positive integer n>=3 do the following in an efficient manner
Generate the corresponding partition graph
Count the total number of nodes and total number of vertices in the partition graph
...
0
votes
1answer
17 views
Is any State Space Tree always Binary Tree?
A backtracking algorithm generates, explicitly or implicitly, a
state-space tree.
Introduction to the design & analysis of algorithms / Anany Levitin
I wonder that whether the saying ...
1
vote
1answer
20 views
On uniform randomness of the weight of the remaining edges of a graph after deleting some of them
Suppose we have a graph $G(V,E,W)$, where $V$ and $E$ are the set of vertices and edges and $W$ is non-negative weight on the edges. Let $w(e)$ be the weight of edge $e$ and $N(e)$ be the neighboring ...
1
vote
1answer
21 views
Manber's graph-partitioning implementation
I'm having trouble understanding a part of Manber's graph-partitioning algorithm, presented in A Text Compression Scheme that Allows Fast Searching Directly in the Compressed File.
Generally speaking ...
0
votes
1answer
22 views
Time Complexity of the Kruskal Algorithm after sorting
In case I have sorted edges already, What is the best time complexity of Kruskal Algorithm?
2
votes
1answer
35 views
Karp hardness of a vector system allocation
Given an undirected graph $G(V,E)$, a vector system is a set $S$ of ordered pair (intuitively called vector) $(u,v)$ (we shall call $u$ the initial point, and $v$ the terminal point) that satisfies ...
2
votes
1answer
24 views
Karp hardness of a guarding set in digraph
Our problem is to decide whether a digraph has a guarding set of size at most $k$. Definitions are following.
A digraph $G(V,A)$ has $V(G)$ as its vertex set and $A(G)$ as its arc set. A guarding set ...
1
vote
1answer
36 views
how to find a node that is known to everyone but doesn't know anyone?
Problem I am trying to solve is this:
There are n nodes, and for every pair of node $X$ and $Y$,
the relation "$X \space knows \space Y$" is either $T$ or $F$. It is possible that "$X \space knows \...
0
votes
0answers
12 views
Compute enclosed space given triangles and vertices in 3D
I have a fairly complex problem and am unsure how to start. Basically I have a list of vertices and triangles. I need to be able to compute enclosing spaces and their areas.
This is my current ...
3
votes
1answer
45 views
Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching?
I came across this problem in Tim Roughgarden's course on Coursera:
In this problem you are given as input a graph $T=(V,E)$ that is a
tree (that is, $T$ is undirected, connected, and acyclic). A ...
0
votes
1answer
16 views
is the alignment between two sequences of points with 'no cross line' constraint an NP problem?
Given two sequences of points(i.e. ordered points), connect the points in seq_A with the points in seq_B according to some rules. A point could be connected to 0, 1, or many points in the other ...
0
votes
0answers
30 views
Finding a minimal subgraph covering all parts of a multipartite graph
I have a large set of nodes $n_i$ and edges $e_{ij}$. Each node can be sorted into exactly one supernode $N_i$ based on a known and fixed parameter.
Nodes within the same supernode have no direct ...
2
votes
0answers
32 views
Edmond's Blossom algorithm (Maximum Matching) explanation
I asked this question on Math Stackexchange but it didn't get much attention, so I am asking it here.
Edmond's Blossom algorithm (Wikipedia), or simply the blossom algorithm, is a popular graph ...
2
votes
1answer
46 views
Digraph vertices: classification by counting outgoing walks
I'm reproducing a question I posted on MSE (yet with no answer both there and by myself).
Given a (finite) directed graph $G = (V, E)$. For each vertex $v \in V$ and a natural number $n$, let $W_v(n)$...
2
votes
1answer
47 views
Optimal assignment of +-1 values to vertices in a graph
Let $(V, E)$ be a simple connected undirected graph, $f: V \to \{-1, +1\}$, and $g: E \to \{-1, +1\}$. The function $g$ is completely defined by $f$, while $f$ is something we get to choose. The only ...
-3
votes
0answers
22 views
Universal Proof graph [on hold]
Can anyone please help me in understanding the below excerpt with illustration? The excerpt comes from paper Automatically Generating Problems and Solutions for Natural Deduction.
Definition 7 (...
1
vote
0answers
13 views
Calculate maximum sum of nodes property with limit on distance being traversed between nodes in a given graph
Given is an undirected weighted graph with N nodes, with each node having a property/Value.
Aim is to find the bestpath which maximizes the sum of the nodes property which can be visited given a ...
1
vote
1answer
26 views
Proof of value discovery in complete graphs
I have an assignment
There are n > 2 finite processors, two registers for each processor.
Register s_i is not readable by the processor p_i but any other processor can read it.
Register r_i is ...
2
votes
0answers
33 views
generalized translation operator on graph [closed]
David IShuman in " vertix-frequency analysis on graph" claims that,"we generalize one of the most important signal processing tools – windowed Fourier analysis – to the graph setting and When we apply ...
1
vote
0answers
26 views
How to handle negative edge weights in distance vector routing protocol with a digraph?
In a Distance Vector routing protocol each node implements a Bellman-Ford inspired algorithm that shares it's routing table (Distance Vector) with each of it's incoming links (upstream neighbors). ...
4
votes
0answers
27 views
Finding the “most modular” subset of graph vertices, i.e. that minimize disagreement inside and outside
Let $G = (V, E)$ be a graph. I want to find the subset of vertices of $G$ that minimizes a certain modularity cost. In our setting, the modularity cost of a subset $X$ is defined as the number of ...
4
votes
0answers
44 views
Inferring ranking functions in a general code graph with partial information
Let me define the notion of call graph:
A program consists on a set of functions $f,g,h,\ldots$ where each
function $n$ is as a mapping $n: D^l \to D^m$. Here $D$ is the
datatype representing ...
6
votes
1answer
46 views
Vertex cover with covering radius 2
Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices?
A vertex included in this vertex cover variant will cover every edge incident to it and every edge ...
-1
votes
2answers
37 views
Graph Coloring Problem
Can solutions to the graph coloring problem be used in the prison system to keep known enemies apart with the goal of reducing violence?
3
votes
1answer
29 views
How would I algorithmically “stretch” polygons on a plane by re-scaling the distances between interior points?
I've been thinking about a computational problem and could use some guidance for how to go about developing an algorithm to solve it.
On a Euclidean plane, I have a polygon A, a set of points A* ...
2
votes
1answer
34 views
Algorithm and Formalism for Most Remote Vertices
In the graph below, N and M are most remote, and H is also an extremum.
Has the problem of finding the most remote vertices been formalized? Could you point me to publications or references on the ...
1
vote
0answers
11 views
Given a simple graph G, what's the quickest known way to sample one of it's spanning trees at random?
Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle.
We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking ...
0
votes
1answer
40 views
Babyface vs Heel
So here's the question: "There are two types of professional wrestlers: "babyfaces"("good guys") and "heels"("bad guys"). Between any pair of professional wrestlers, there may or may not be a rivalry. ...
4
votes
1answer
65 views
Karp hardness of searching for a matching split
UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC ...
4
votes
1answer
34 views
Karp hardness of searching for a matching erosion
First, read the previous question: Karp hardness of searching for a matching cut
As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the ...
1
vote
3answers
59 views
Optimizing coin splitting - Is this algorithm as fast as I think?
In a recent exam, I've been asked to solve the following problem:
The problem
Two players play the following game: Given a sequence of coin values
$v_1,\ldots,v_n (n \vert 2)$ the players ...
0
votes
1answer
30 views
DFS on reversed graph
I was watching a lecture on determining the strongly connected components of a graph using Kosaraju's algorithm and the lecturer claimed one can easily walk the edges in reverse fashion.
While I see ...
6
votes
2answers
82 views
Karp hardness of searching for a matching cut
Follow-up question in the series:
Karp hardness of searching for a matching erosion
Karp hardness of searching for a matching split
Maximum Matching Cut problem
Input: An undirected graph $G(...
0
votes
0answers
33 views
Directed Acyclic Graph - Longest path in a DAG represents minimum number of steps to list all the vertices in groups
Longest path in a dag represents the minimum number of steps to list all the vertices in groups.
Can any body provide a proof or just explain why its happening ?? In the image below the nodes of the ...
0
votes
0answers
13 views
Equation to manage non weighted flow
I have a graph like the one below:
This represents nodes linked by path. One node stands for the start (on the left) and the other for the end (on the right).
My goal is to send troops from the ...
2
votes
1answer
69 views
Detect non existence of a cycle in a graph using Datalog : SMTLIB Format for Z3
I want to detect the non existence of a cycle in a graph using Datalog (which is a declarative logic programming language).
The proposed solution was:
...
