Stack Exchange Network

Stack Exchange network consists of 174 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 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

How to find the v.key in queue of Prim's Algorithm

How to find the v.key in constant time? ...
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: ...