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

learn more… | top users | synonyms

0
votes
0answers
8 views

What do L1, L2, and L3 mean in Johnson's Algorithm for finding elementary circuits of a directed graph?

In his paper, Donald B. Johnson mentions in his psuedocode parts which he refers as L1, L2, L3. What are they?
2
votes
1answer
22 views

Is there a way to reflect small edge-weight changes after computing Floyd-Warshall on a large graph?

I am working on a hex-based game in which I'm trying to pre-calculate pathfinding for a given map using the Floyd-Warshall algorithm. The map size is on the order of thousands of hexes (so maximum ...
2
votes
1answer
21 views

Flaw in linear programming solution for multi-commodity flow problem?

The multi-commodity flow problem problem statement - wiki According to constraints of multi-commodity flow problem a given material must start at source s with demand d and end up at its target t. ...
-3
votes
0answers
25 views

Number of ways to construct a Regular graph

For a regular graph (each vertex has same degree k), a part of graph upto level l is given, how to compute the total number of ways in which the graph can be completed given that m edges and n ...
-1
votes
0answers
13 views

Tarjan's Bridge Finding Algorithm Psuedocode? [on hold]

I was looking for a verbose and well-constructed psuedocode for finding Bridges in an undirected Graph. If possible please share any psueodocode, thank you!
0
votes
0answers
10 views

Does marginalizing on a Bayesian network preserve its original independence assumptions?

I know that marginalizing over a Bayesian network causes changes to the graph (e.g. marginalizing node c in the V-structure given by $a \rightarrow c \leftarrow b$ results in $a$ and $b$ being ...
1
vote
0answers
18 views

Reconstructing a graph from set of sequences of edges

I have posted the same problem to Math Overflow, not sure where it fits better. I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, ...
1
vote
0answers
22 views

probability that the vertex set {1,…,k} is component of random graph

Consider a graph with vertices 1,...,n and suppose that each of the $\binom{n}{2}$pairs of vertices is, independently, an edge of this graph with probability p.Let $P_n$ denote the probability that ...
0
votes
1answer
62 views

Voronoi Diagram: Exactly 2n-5 vertices

I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices. I tried to use the Euler ...
1
vote
0answers
22 views

Variable elimination in Bayesian network

I'm trying to check if my understanding of variable elimination is correct. Assume the above Bayesian network is factorized as: $p(a,b,d,e,l,s,t,x) = ...
3
votes
0answers
61 views

How to determine Isomorphism of Non-Symmetric Matrix when Permutation-Set is given?

Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not equal. ...
1
vote
1answer
29 views

Minimum Weight Directed Subgraph ensuring all pairs reachability?

After some work on Minimum Spanning Trees and Steiner trees in combinatorial problems I came across this problem that I would like to look further in my research, but I want to know if there is an ...
2
votes
2answers
150 views

Basic questions about network flow calculations

Flow networks are often constructed when one is interested in measuring how resilient a graph is. The idea goes as follows: two vertices are designated as source $(s)$ and sink $(t)$ respectively, to ...
1
vote
2answers
72 views

Linear-time algorithm to find an odd-length cycle in a directed graph

Problem: Give a linear-time algorithm to find an odd-length (directed) cycle in a directed graph. (Exercise 3.21 of Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.) The related ...
1
vote
1answer
30 views

Relation between MAX CUT and MIN CUT

I'd like to ask a question about MAX CUT and MIN CUT on graphs with unit edge-weight. I know that MAX CUT is NP-Hard, but MIN CUT is in P (i think)? Barahona, in 1982, showed (Lemma 1) finding a cut ...
0
votes
0answers
16 views

Finding edge disjoint spanning trees in certain graphs

I'm studying the problem of finding edge-disjoint spanning trees in a given graph. I would like to compare the performance of matroid partitioning algorithm that can be used to solve this problem and ...
1
vote
0answers
21 views

What is the psuedo-code for Tremaux's Algorithm as a Depth First Search to solve a maze?

I was interested in the Tremaux Algorithm as a Depth First Search to solve a Maze. Unfortunately I was not able to understand what Data Structures are and how they could be used. For example, I saw a ...
3
votes
0answers
21 views

How to compute amortized complexity of n runs of Dijkstra's algorithm?

I'm trying to figure out how to compute an amortized complexity/ or complexity of this algorithm. We have a Graph which is oriented. And we are going to run Dijkstra's algorithm for finding a shortest ...
1
vote
2answers
51 views

Equivalent definition of minimal spanning tree

Prove that $T$ is MST $\Leftrightarrow$ for any edge $uv \notin T$, $uv$ has the maximal weight on the cycle created by adding $uv$ to $T$. It's my attempt to prove $\Rightarrow$: Consider the ...
0
votes
1answer
27 views

What do we mean when we say an edge (u,v) connects some component to other component in forest G = (V,A)

Let H = (V,E) be a connected, undirected graph. Let A be a subset of E. Let C = (W , F) be a connected component (tree) in the forest G = (V,A). Let (u,v) be an edge connecting C to some other ...
1
vote
1answer
22 views

How do I find the intersection of subgraphs in a directed acyclic graph efficiently?

I have a directory structure in which each directory can have multiple parents (IOW, a cd .. is ambiguous). AFAICS this means this is equivalent to a directed ...
1
vote
0answers
24 views

Generate a graph to exact size using Kronecker product graph model

In network science, we can take sample a complex system and derive from this sampling a representative network (or graph) that describes the system to some extent. A model of a network, is a powerful ...
3
votes
1answer
26 views

Ford-Fulkerson algorithm with asymmetric adjacency matrix

Suppose that I have a bipartite graph $G=(A \cup B, E)$ and $A = \{1, 2, \dots, n\}$, $B = \{1, 2, \dots, m\}$. After a virtual sink $s = 0$ and a source $t = n+1$ is included into the graph, I want ...
7
votes
0answers
64 views

Optimal meeting point in directed graph

Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$. I need ...
0
votes
1answer
77 views

Complexity of the Dijkstra algorithm

I'm little confused by computing a time complexity for Dijkstra algorithm. It is said that the complexity is in $O(|V|^2)$ - Wikipedia - Dijkstra, which I ...
5
votes
2answers
84 views

Efficient algorithms for identifying the diamond fork&join vertices and the diamond pairs in directed acyclic graph?

Given a DAG (directed acyclic graph) $G=(V,E)$ without multiple edges, i.e., edges with the same source and target vertices, we define: A vertex $v_j \in V$ is a diamond-join ($\Diamond_J$) vertex if ...
-1
votes
1answer
24 views

Let G be k-reguler bipartite graph of degree at least 2. show that K(G) not equal 1? [closed]

Let G be k-reguler bipartite graph of degree at least 2, for all v belong to V(G) prove that k(G-v) is connected?
0
votes
0answers
37 views

How to find maxflow with minimum number of edges?

I am struggling with the flowing problem: You are given a source s and a sink t and a biparted graph G. All vertices {v} from the left half are connected to the source s with given capacity C[v]. ...
4
votes
0answers
40 views

find a minimum-cost pair of arc-disjoint paths, both within a given restricted distance

Is there a polynomial algorithm that can find a pair of arc-disjoint paths in a directed graph that has a minimum total cost, subject to the condition that both paths are within the same distance. ...
1
vote
1answer
33 views

TSP Edge Removal

Are there any papers/algorithms for finding edges in a graph that can be removed with affecting the graph's optimal TSP tour length? For instance, in a Euclidean TSP instance, many edges could be ...
3
votes
0answers
12 views

Minimal Steiner Tree in unweighted directed graph

I have an unweighted directed graph $(V, E)$ and a subset $T \subseteq V$ of these vertices. I want to find the minimum tree $(V',E')$ that contains all these $T$ vertices (minimize in number of nodes ...
1
vote
1answer
80 views

Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with $N$ vertices and $M$ edges. Each edge has its own weight and colour. There are at most 10 different colours in the whole graph. Each time I traverse edges of ...
4
votes
0answers
105 views

Vertex Disjoint Path Covers of Hypercube-Like Graphs [migrated]

This is a followup question relating to an older question I posted, namely: Decomposing the n-cube into vertex-disjoint paths. Given a graph $G = (V, E)$ and sets of distinct vertices $S = \{s_1, ...
0
votes
0answers
8 views

Should all internal node keys in B+ tree also be in the leaves?

I was reading about B+ tree insertion. The algorithm takes following form: Insert the new node as the leaf node. If the leaf node overflows, split the node and copy the middle element to the ...
1
vote
2answers
37 views

Is there a name for graphs which contain oriented and non-oriented edges?

Is there a name for graphs which contain oriented and non-oriented edges? I couldn't find on the internet if there exist a specific name for such graphs.
1
vote
1answer
46 views

Algorithm to find a path connecting given nodes in a graph

Suppose I have $n$ nodes in a graph and I identify $x$ nodes in the graph (where $x < n$). I would like to find a path to connect all those $x$ nodes I have identified. Is there any algorithm for ...
0
votes
1answer
33 views

Facts about internal and external path lengths of binary tree

While learning binary tree's properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search. My book specifies some ...
1
vote
1answer
38 views

What does a ball of center v and radius r with at most r hops away mean?

I am trying to understand what that sentence means. Intuitively, its obvious a radius ball means in a $ \mathbb{R}^{n}$ with respect to some norm. Its just the following set: $$ B(v, r) = \{ x \in ...
0
votes
1answer
27 views

Can an independent set (of vertices) be a vertex cover as well?

I wanted to clarify if this is possible, so I thought about a possible vertex cover that can also serve as an independent set: So, to clarify, am I right to say that the nodes in red are both (i) a ...
0
votes
1answer
25 views

Would incrementing the min cut edges by 1 increase the max flow by 1 as well?

Given the theorem that max flow <= min cut, Would incrementing the min cut edges by 1 increase the max flow by 1 as well?
4
votes
1answer
80 views

Find all non-isomorphic graphs with a particular degree sequence

I have a degree sequence and I want to generate all non-isomorphic graphs with that degree sequence, as fast as possible. The only way I found is generating the first graph using the Havel-Hakimi ...
6
votes
0answers
122 views

How to solve the loan graph problem

The problem A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...
0
votes
0answers
44 views

Find closed loops in an undirected graph given an adjacency list

I am trying to find all the cycles in an undirected graph given the adjacency list of the vertices, with the an output of all the cycles in form of the vertices they are made up of. For example ...
0
votes
1answer
21 views

Check Cycles- On adding an edge in DAG

Given a DAG N, if an edge $(U \rightarrow V)$ is added between any existing nodes U and V. Then, by performing DFS from the node $U$ and checking whether there is a cycle or a not, should be ...
-1
votes
3answers
90 views

Terminology for trees

In a tree, I want to refer to a particular child of a node, the child of this child, the child of this child of this child, and then the child of this child of this child of this child. For instance, ...
2
votes
1answer
29 views

Determining minimum number of edges to remove in a bipartite graph so the maximum path length is 2

I stumbled upon the following problem during my research. I have a bipartite graph, and I want to determine the minimum number of edges to to remove so that the maximum path length in the resulting ...
4
votes
1answer
40 views

Can we always reduce the weights of a weighted graph to rationals and preserve equality relationships?

Let $G = (Q, \Delta, W)$ be a finite weighted graph with $\Delta: Q \times Q$ and $W: Q \times Q \to \mathbb{R}^{+}$. Is it the case that there always exist a function $W': Q \times Q \to ...
1
vote
1answer
29 views

Can minimum or maximum height of the binary search tree be constrained by the position of some elements

I came across one problem, which read as follows: We want to place the 13 letters A, B, C, D, E, F, G, H, I, J, K, L, M in a binary search tree with the minimum number of levels: 4. Because there ...
1
vote
1answer
61 views

Markov Chain Mixing Time of the Complete Graph

I'm having a hard time understanding mixing time for Markov Chains on Complete Graphs (Kn). We can define the probability matrix for Kn where Pi,j=probability of going from i to j (technically ...
3
votes
1answer
92 views

How many number of different binary trees are possible for a given postorder (or preorder) traversal

I came across the problem: What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A,B,C? Now 3 being small number I was quick to draw all possible ...