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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.

1
vote
2answers
35 views

Probability that a random graph will remain planar after adding an edge

According to this answer, a random graph on $n$ vertices is a graph which has each of the $n\choose2$ edges independently with probability $1/2$ each. The probability of at most $3n-6$ edges (which is ...
1
vote
1answer
49 views

Split graph in two parts, such that most nodes have even number of edges

We have given graph of at most $200$ nodes, we want to split the given graph in two parts, such that the number of nodes with even number of edges is maximized, note that the edges that are between ...
5
votes
0answers
47 views

Constructing a connected graph with given degree sequence

I am interested in constructing simple connected graphs where each vertex has a fixed number of edges (degree) ahead of time. I had originally assume I could use some modification of the Havel-Hakimi ...
1
vote
2answers
77 views

Super-strongly connected components?

I face a problem that is related to (strongly) connected components. Let $G=(V,E)$ be an undirected graph. I want to find subgraphs $G_1,G_2, \dots,G_n$ of $G$ such that they do not overlap (i.e. ...
3
votes
1answer
48 views

Longest path with limited edge traversals

Given a graph where each edge has a capacity, is there an efficient algorithm to find the longest path in the graph which does not pass through an edge more times than its capacity? The exact problem ...
0
votes
0answers
22 views

L1 sampling for sampling edges of a graph

I am trying to sample the edges of an undirected graph using weights. The goal is to run a sparsification algorithm on the graph. I see the point that L1 norm is best for sparsification. Can someone ...
1
vote
1answer
18 views

Obtaining Max-Weight Matching from Max-Weight-Max-Cardinality Matching?

I have a graph with integer-valued edge weights (possibly negative) on which I would like to obtain a maximum-weight matching. However, I am using python-graph-tool, which only has max-cardinality ...
1
vote
0answers
20 views

Minimum weight Hamiltonian path on a weighted (0 and 1) tournament graph

Suppose we have a weighted tournament graph. (A directed graph in which every pair of distinct vertices is connected by a single directed edge.) The weights are constrained to be 0 and 1. I know ...
-1
votes
1answer
17 views

Finding a Hamilton path in a Complete Euclidean Graph is in P

How is it possible to prove that this assert is not true?
1
vote
1answer
17 views

Marginalise edge weights on graph

I have a directed acyclic graph with a score on each edge. The score of a path is defined to be the sum of the scores on the edges along this path. The probability of a path is the score of such a ...
2
votes
0answers
37 views

Finding maximum weighted n disjoint cliques

Maximum weight clique problem has some attention but i could not find any efficient approaches to this problem yet. I acknowledge that it is np-hard, but are there any known approximations? Given a ...
4
votes
1answer
37 views

Can Depth-first search (DFS) with alphabetical traversal of neighbors be run in O(|V|+|E|) time?

I feel like the answer is no but I'm not sure. I think it's commonly accepted that DFS runs in $O(|V| + |E|)$ time. I've read a few explanations and they all make sense if the neighbour traversal for ...
0
votes
1answer
42 views

Subgraph Isomorphism checking in Multigraphs

I am considering the following problem: Input: 2 Graphs G=(V,E), H=(V',E'). G and H are directed multigraphs Question: Find a subgraph in G which is isomorphic to H Is there any algorithm ...
0
votes
0answers
27 views

How many roots are there in an undirected root

Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
4
votes
1answer
51 views

Complexity of a graph parity-coloring problem

Suppose I have a positively weighted (bounded-degree) graph $G$ where each vertex in $G$ is colored either black or white. I'm curious about the complexity of the following problem: Find a subset $S$...
3
votes
1answer
59 views

Dependent Type Theory Implementation of a Graph

In Haskell you find graphs defined like this: data Graph a = GNode a (Graph a) Or this: ...
1
vote
1answer
30 views

If the parent in a bridge is the root, is it a bridge cut node?

I am going through Professor Skiena's textbook and he says that there are 3 types of cut-nodes - root, bridge cut node, and parent cut node. Now if the earliest reachable ancestor from a node is ...
0
votes
0answers
32 views

Is “Clean Graph” a Thing?

My professor uses the term "clean graph" to mean that the nodes have no idea of the topology. Each node is aware of its ID, but has no idea about parents or edges and so on and it has to discover. Is ...
2
votes
2answers
37 views

Find out an algorithm that finds out if an undirected graph contains even length cycle or not using BFS?

I know how to find odd length cycles(a bipartite graph cannot have odd cycles) but I cannot manage to make an algorithm when considering even length cycles.
0
votes
0answers
27 views

What is the Time Complexity of a Node Learning the Topology of a Graph

O(Diamater) is the time complexity for any node to receive a message from any other node. If there is such an algorithm that every node flooding a message consisting of some information about the ...
0
votes
0answers
27 views

Measuring how “balanced” a binary tree is

I have some binary trees, and I'm looking for a metric to quantify how "balanced" a tree is. I don't have a rigorous definition for "balanceness", but my intuition suggests it's a measure of how close ...
2
votes
1answer
20 views

How many different strongly connected graphs can be created given n nodes?

Given some fixed number of nodes $n$, which we will number 1 to $n$ in order to tell them apart, how many different strongly connected graphs can be created? Multiple edges with the same starting and ...
0
votes
1answer
12 views

Asymptotic Time Analysis for BFS Tree

Suppose I want to broadcast from my root to all the nodes in a BFS tree. What is the time complexity of this process? I know that it is suppose to be proportional to the depth of the tree, like O(...
2
votes
1answer
352 views

Is De Bruijn Graph Hyper-cube?

I do not know if I miss something in the definition of a hyper-cube, but as far as I understand, Hyper-cube graphs have 2^n vertices and if written in binary form, "one-bit difference" strings of ...
4
votes
1answer
373 views

Clique vs Complete Graph

Is there a difference between a complete graph and a clique topology? As far as I understand, both refer to graphs in which every possible edge between any two vertices is present. Is there a subtle ...
0
votes
1answer
29 views

The relationship between degree and the number of leaves of a tree?

What is the relationship between $\text{deg}(T)$ and the number of leaves of $T$, if $T$ is a tree?
0
votes
1answer
30 views

A tree which each node selected as a root results in a different topology?

Show that, for every n >= 7, there exists a tree of n non-labeled nodes such that picking each of the n nodes as a root results in a different rooted tree.
2
votes
1answer
31 views

Centre, diameter, and radius of graph

I have been thinking a lot on some questions related to centres, diameter ($D$), and radius ($R$) of an undirected connected graph, but couldn't find anywhere the answers, so am posting here. Ques1. ...
0
votes
0answers
18 views

Implementation/explanation of the hub based labelling algorithm

I've found plethora of papers describing the performance advantages and basic correctness proofs of the hub-based labelling shortest path algorithm. However I'd like to implement the algorithm, and ...
1
vote
2answers
47 views

Shortest travelling cost if we have bunch of points in 2D plane

I got this question in an interview recently. I was given a bunch of points (for eg.- Start(88, 81), Dest(85,80), P1(19, 22), P2(31, 15), P3(27, 29), P4(30, 10), P5(20, 26), P6(5, 14)) on a 2D plane ...
0
votes
1answer
29 views

Given all maximal independent sets of a graph, find the maximum indepdent set

I am new to this independent set problem in graph theory. As per my understanding so far an independent set is a set of vertices in which no two vertices are adjacent. And the maximal independent set ...
0
votes
0answers
30 views

mLP to mAGTSP formulation

In the paper Scheduling Twin Yard Cranes in a Container Block authors provide a mILP to solve scheduling twin cranes to execute requests in a block at a seaport to minimize makespan of the cranes. ...
2
votes
1answer
43 views

Prove np-hardness of dividing items from the lists

I have a problem: There is finished number of lists of items. The same item can be on many lists. I would like to color items (there are 3 available colors) that on every list there are items in at ...
1
vote
0answers
29 views

How can I find matchings in a Bipartite graph beginning with specific vertices?

Context: I'm modelling kidney exchanges through directed acyclic graphs. I convert these to Bipartite graphs (by splitting each node into a donor and receiver, and the edge from the original graph ...
1
vote
1answer
30 views

Need pointers for problem formulation

I have very little experience with graph DBs but i imagine this problem suits one Assume a dataset with two entities , Users and Foods. A user can have a relationship with a Food, specifically they ...
0
votes
0answers
21 views

Efficient algorithm for constructing the Edge-Adjacency Matrix

I've been recently working with graph, more precisely edge-adjacency matrices. I found this source, which explains the concept intuitively. Now, when I am trying to implement this conversion, I was ...
3
votes
3answers
99 views

Minimal number of nodes needed to connect a disconnected graph

Given a graph $G = (V, E)$ with $V = U \uplus T$ (let's say the vertices are labelled $U$ or $T$), I am looking for the smallest set $U' \subseteq U$ such that $G[U' \cup T]$ is connected. If we ...
0
votes
1answer
34 views

Add a road to a network (Graph problem with Dijkstra)

Recently i have found a problem stating: There is a network of roads G=(V,E)(it is not directed) connecting a set of cities V. The length of each road e ∈ E is le. There is a proposal to add one new ...
3
votes
1answer
23 views

Minimum number of moves required to transfer items from source bins to target bins?

I have a set of source bins, each with some number of items, and a set of target bins. I want to move all of the items from the source bins to the target bins, using the minimum number of moves. ...
1
vote
1answer
13 views

Finding pair of non-adjacent cliques in a dense graph

I have a graph consisting of about 5000 vertices, with density around 0.5. I'm trying to find two disjoint 6-cliques, which are not connected by an edge. I have tried bruteforcing this, by firstly ...
1
vote
2answers
16 views

Explanation about the condition for connectivity in Erdos Reyni model

I am currently studying the Erdos-Reyni model, the $G(n,p)$ model to be specific. Its easy to understand that all graphs with $m$ edges have generating probability of $p^{m}(1-p)^{n(n-1)/2 - m}$ ...
1
vote
1answer
48 views

is it necessary to cover all the verticies in eular path?

I was going through graph theory and came across the term Euler path or some people prefer Euler trail as vertices can repeat. According to the definition from wiki (https://en.wikipedia.org/wiki/...
1
vote
1answer
73 views

If a connected graph has a bridge then it has a cut vertex

Is it true that if a connected graph has a bridge then it has a cut vertex? In my point of view, I don't think it is true to consider that a graph having a cut edge will definitely have cut vertex. ...
2
votes
1answer
17 views

Is every planar graph a possible dual graph of a voronoi diagram?

My question is: Given a planar graph defined by its adjacency matrix. Can I always find a set of points, so that the dual graph of the voronoi diagram of that set of points is the same as the planar ...
0
votes
0answers
21 views

Algorithms for discrete scheduling problems?

I was wondering what the go-to algorithms are for discrete/combinatorial scheduling problems? An example of the type of problem I'm interested in is optimally routing agents from their starting ...
4
votes
0answers
81 views

graph signal processing

What's the intuition behind a ''Graph fourier transform'' ? I'm not so much interested in mathematical details or technical applications. I'm trying to grasp what a graph fourier transform actually ...
0
votes
0answers
14 views

reference to model a network which nodes handle processing

does anybody have a basic reference (if it is possible) that explain how to mathematically model the state of a network. I assume that it goes like modeling a graph that is composed by nodes and edges....
0
votes
1answer
28 views

Finding independent set of size n in an undirected graph

Is there an algorithm that, given an undirected graph, finds an independent set of size n (where n is less than or equal to the total number of vertices)?
1
vote
2answers
42 views

Generate all sub paths

I have a path from node 1 to node n, which I can represent as a set: S = {1, 2, ..., n-1, n}. I want to efficiently generate the set of all subpaths from 1 to n. For instance, for n=5, we have S={1,2,...
-1
votes
1answer
18 views

Independence groups and fully connected groups

Let G be a connected graph, knowing that it has more than 9 vertex, Show that either its independence number is bigger-equal than 4 or its click number (the size of the biggest fully connected group) ...