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

2
votes
0answers
13 views

Cheeger constant of a graph versus conductance of a Markov chain

Given some graph $G$ with vertices $V$ and edges $E$, its Cheeger constant $h(G)$ is well defined as $$ h(G) = \min_{S\subset V,0<|S|\leq|V|}\frac{|\partial S|}{|S|}. $$ Given some ...
1
vote
1answer
19 views

Finding Connected Components Dependent on Order?

It seems to me that the outcome of a connected components algo is dependent on the start vertex. Is this correct? Say we had the graph If we started our connected component search from the vertex ...
0
votes
0answers
25 views

Does it exist directed graphs were the likelihood of edges crossing other vertices is likely to be small? [on hold]

In the scope graph visualising with software, are there classes of directed graphs that given a node the likelihood of it's edges crossing other vertices in the graph is small when drawing the graph. ...
1
vote
1answer
22 views

Is a graph of zero nodes/vertices connected?

Suppose there is a graph G of zero nodes, there is an even number of nodes. By definition of connectivity, the graph G is connected when there is a path between every pair of nodes. But there are no ...
0
votes
0answers
17 views
1
vote
0answers
24 views

Finding if a feasible flow exists in a minimum cost flow problem

I've been trying to understand the generic methodology for finding a flow with a certain value (satisfying all demand criteria) with a minimum corresponding cost. I know that this might sound somewhat ...
14
votes
0answers
34 views

Is there an efficient algorithm for this vertex cycle cover problem?

I've been trying to find an algorithm to find a maximum vertex cycle cover of a directed graph $G$ — that is, a set of disjoint cycles which contain all the vertices in $G$, with as many cycles as ...
1
vote
0answers
32 views

The relationship between degree of vertex and size of dominating set [closed]

I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has ...
22
votes
0answers
367 views

Imagine a red-black tree. Is there always a sequence of insertions and deletions that creates it?

Let's assume the following definition of a red-black tree: It is a binary search tree. Each node is colored either red or black. The root is black. Two nodes connected by an edge cannot be red at ...
5
votes
4answers
12k views

Why can't DFS be used to find shortest paths in unweighted graphs?

I understand that using DFS "as is" will not find a shortest path in an unweighted graph. But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? ...
1
vote
1answer
34 views

Reduce Min-Cut to 0/1 Integer Program

Given an undirected, weighted graph $G=(V,E)$ and two nodes $s,t \in V$ and weight function $w: E \rightarrow \mathbb{N}$. The weight of a (s,t)-cut $ (U, U^C)$ is given by: $$ w(U,U^C) := ...
0
votes
1answer
21 views

Generate random weighted graphs representing a road network

in order to solve a DARP problem I created a Python class, that can generate random graphs. I attribute a random number to every edge which represents the cost to travel over that edge. My current ...
0
votes
1answer
45 views

Detecting all cycles in un-directed graph [duplicate]

I would like to detect all the cycles(non duplicate) in a given graph, I mean if A-B-C-A is a cycle, then A-C-B-A is a duplicate of previous one and need to be considered.I could use DFS and detect a ...
1
vote
2answers
266 views

Determining Length of a walk in Nondeterministic Finite Automata with Lambda Transitions

I am learning about CS Theory and specifically Nondeterministic Finite Automata (NFA) right now. In my book I came across a section of text that discussed a way to determine the length of a walk ...
0
votes
1answer
215 views

Bottleneck TSP with MST

There is a problem I don't know the answer too. The 3 approximation for the bottleneck TSP that involves first getting the MST. I have not been able to come up with the right "shortcut" method so far. ...
4
votes
1answer
131 views

Importance of a person to another person in social network

In social network (an unweighted indirect network), is there some measure of importance of a person A on another person B, ...
6
votes
1answer
610 views

Why is the complexity of negative-cycle-cancelling $O(V²AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
3
votes
1answer
34 views

Expected number of independent sets of size $k$ in random graph $G(n,p)$

I am looking for a formula for determining the expected number of independent sets of size $k$ (for arbitrary $k$) in a random graph $G(n,p)$. Here $n$ is the number of vertices and each edge is ...
5
votes
1answer
680 views

Maximum Independent Subset of 2D Grid Subgraph

In the general case finding a Maximum Independent Subset of a Graph is NP-Hard. However consider the following subset of graphs: Create an $N \times N$ grid of unit square cells. Build a graph $G$ ...
1
vote
1answer
15 views

Efficient algorithm to generate undirected graph edges from 3D distribution of nodes based on distance

I have a set of nodes where each node $n_i$ is associated with a cartesian coordinate $\vec r_i$ and a radius $\sigma_i$. I want to generate a graph data structure where nodes $n_i$ and $n_j$ are ...
2
votes
2answers
31 views

Shortest path in divisors graph

There is a graph with N vertices numbered from 1 to N. Edge between a and b exists if and only if a|b or b|a. If a|b then the weight of the edge is b/a. If b|a then the weight of the edge is a/b. ...
4
votes
1answer
108 views

Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

I'm currently reading introduction to algorithms and came by Johnson’s algorithm that depends on making sure that all paths are positive. the algo depends on finding a new weight function (w') that ...
5
votes
0answers
63 views

Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function. The answer ...
2
votes
2answers
114 views

Longest cycle in a digraph

Given a directed graph $G$, we want a (simple) cycle in $G$ of maximal length. The cycle does not need to be an induced subgraph of $G$. What is known about this optimization problem? Do we know its ...
-1
votes
1answer
40 views

Longest path with at most $k$ edges in a tree

How to find the longest (in terms of sum of weights) simple path with at most $k$ edges in a tree? Weights of edges are integers, so they can be negative. I thought about using Bellman-Ford, but it ...
4
votes
1answer
134 views

Unique path sums in a DAG using vertex instrumentation

I stumbled across this paper from Ball et al. In their paper they assign specific values to the edges of a graph. When the graph is traversed, or lets call it executed (since they talk about control ...
2
votes
1answer
125 views

what is the k-line-connected graph definition

What is the definition for k-line-connectedness of the graph ? I am in doubt whether it differs from usual k-vertex (edge) connectedness. I've encountered it in the paper titled "Np-complete problems ...
2
votes
1answer
54 views

Connecting an unconnected forest of subtrees in a graph?

If I have a weighted graph $G=(V,E)$ and three subgraphs $T_1$, $T_2$ and $T_3$ in $G$ which are trees and all unconnected from each other. What is the best way to connect these three trees such that ...
2
votes
2answers
109 views

Is there a name/algorithm for this problem related to set cover and CSP?

Our college would like to determine if a transcript contains classes that satisfy every general education requirement. What makes this nontrivial is that while a single class may in theory satisfy ...
1
vote
2answers
83 views

Find hamilton cycle in a directed graph reduced to sat problem

I need to find a Hamiltonian cycle in a directed graph using propositional logic, and to solve it by sat solver. So after I couldn't find a working solution, I found a paper that describes how to ...
4
votes
1answer
125 views

Terminology for a graph with ports on its nodes

A Graph is a well-defined concept in mathematics, computer science and engineering disciplines that depend on them. However, oftentimes a practical implementation of a (directed) graph in a certain ...
2
votes
1answer
64 views

Closed Walk in Planar Graphs

Input: Planar graph $G$ and its embedding in sphere $\Pi$, edges $e, f \in E(G)$ and integer $k$. Output: The set of closed walks in $G$ using $e$ and $f$ which contains $k$ faces of $G$. In other ...
5
votes
0answers
88 views

minimizing computations for evaluating two polynomial simultaneously

I want to evaluate two polynomials $f$ and $g$ simultaneously, on the same input (in a computer program). These polynomial have only coefficients $0, 1, a , b$ and their degree is less than 700. I ...
3
votes
0answers
44 views

Closed walk in planar graphs that contains k faces

Input: Planar graph $G$ and its embedding in sphere $\Pi$, edges $e, f \in E(G)$ and integer $k$. Output: A shortest closed walk (one among possibly many, if exists) in $G$ using $e$ and $f$ which ...
1
vote
1answer
55 views

Scheduling distributed computational graph

I work in computational fluid dynamics. And I spend most of my time waiting for simulation to complete. The common way to improve simulation performance is to use a suitable distributed linear ...
5
votes
1answer
136 views

Generate a random graph with geometrical degree distribution

I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper. We are talking about generating an undirected graph in a slightly different way ...
0
votes
2answers
498 views

Minimum size of largest clique in graph

I'm having trouble with a problem from HackerRank, and I'm hoping someone here can enlighten me. The problem is stated like this: What is the minimum size of the largest clique in any graph with N ...
5
votes
2answers
99 views

How to generate graphs with a Hamiltonian path?

I need to create a graph generator for my next project. Generally algorithms are trying to find a Hamiltonian path in a graph. So I can create a graph generator, generate a graph, and then I can ...
5
votes
1answer
117 views

Partition a bipartite graph to a complete matching and an independent set

I am looking for a reference for the following theorem: Let $G$ be a bipartite graph with partitions $X$ and $Y$, each with the same number of vertices ($n$). There is a nonempty subset $Y_1 ...
3
votes
1answer
32 views

Is there a name for the problem of spatially organizing a graph as to minimize total edge length?

The problem is that of spatially (with or without a fixed spatial dimension) organizing a graph so that each node becomes a cell in a grid, and each edge becomes a line, such that the total combined ...
1
vote
1answer
72 views

Prim's algorithm: difference between brute force and PQ approaches

I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues. Given a graph $G=(V,E)$, the former can be ...
3
votes
2answers
124 views

counterexample for this graph isomorphism algorithm

I'm trying to learn about graph isomorphism and I stumbled upon coloring. When given 2 graphs, you give each vertex a color according to properties of their neighbors and any vertex on graph 1 can ...
6
votes
4answers
419 views

XOR-like behavior in flow networks

XOR is not the correct name, but I am looking for some kind of exclusive behavior. I am currently solving a set of different (assignment) problems by modeling flow networks and running a ...
2
votes
0answers
19 views

maximum flow with all or nothing through each edge

Consider a maximum flow problem, where each edge has a small integer capacity. Now, I want a solution that for each edge uses the entire capacity, or no flow through that edge at all. To avoid the ...
4
votes
1answer
36 views

Variations of Depth First Travesal

While learning depth first traversal, I realise there are two approaches that are followed. Method 1. The first one is as given in the Forouzan's book is as follows: Push the initial node onto the ...
0
votes
0answers
14 views

How to extend the number of tourists we can extrade in an uprising country by understanding the concept of min-cut in graph theory?

Good evening, I have some difficulty to understand the idea of what are minimum cut when trying to improve the number of tourist. Okay, let's say we had 200 tourists having fun in the imaginary ...
1
vote
0answers
25 views

Data structure to store a large power-law graph with constantly updated structure

I am looking for data structures to store power-law (hence mostly sparse, but few dense too) graphs whose structure is continuously being modified, including new vertices being added and edge weights ...
2
votes
0answers
85 views

Vertex-disjoint cycles passing through a collection of vertices

I am wondering about the complexity of the following problem: given a directed graph $G=(V,E)$ (which may have self-loops at some vertices) and a subset of the vertices $U \subset V$, does there exist ...
5
votes
3answers
490 views

Counterexample to this modified Dijkstra's

In class, we were given the following problem: We are given a directed graph G = (V, E) on which each edge (u, v) ∈ E has an associated value r(u, v) which is a real number in the range 0 ≤ r(u, ...