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

1
vote
0answers
6 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
17 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
21 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
16 views

I have a graph i need to find minimum spanning [on hold]

.... but some edges have not weight. How should i consider them?
1
vote
0answers
23 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 ...
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 ...
0
votes
1answer
20 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
44 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 ...
14
votes
0answers
29 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 ...
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 ...
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 ...
4
votes
1answer
106 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 ...
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, ...
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. ...
5
votes
0answers
62 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 ...
-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 ...
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 ...
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
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 ...
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
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) := ...
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 ...
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 ...
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
2answers
143 views

Confusion in CLRS's version of Prim's algorithm

The algorithm is as follows: ...
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 ...
5
votes
2answers
98 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 ...
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 ...
0
votes
1answer
34 views

Examples of maximal paths in undirected graphs

According to me, maximal paths in a graph are those paths which cannot be included in any other larger paths. Could anyone please explain me this with some examples? Also what would happen if the ...
0
votes
2answers
43 views

Relation between number of edges and vertices in a DAG

I conjecture that, in a Directed Acyclic Graph, $O(|V|) = O(|E|)$. Is this statement correct, can it be refined? This is probably standard material; is there a simple reference about this?
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 ...
1
vote
0answers
47 views

When is the output of shortest path $\subset$ MST?

I was wondering if the output of an algorithm like Dijkstra was always contained in the minimal spanning tree, however, a counter example to this claim are cyclic graphs like: The shortest path $B ...
4
votes
1answer
39 views

Why is bipartite perfect matching a special case of clique problem?

In Lovász writes [1] : bipartite graph has a perfect matching, which is a special case of the clique problem Why is bipartite perfect matching a special case of clique problem? The Work of ...
4
votes
3answers
91 views

Non planarity of K3,3

I am reading about planar graphs from this site. It says: The complete bipartite graph K3,3 is not planar, since every drawing of K3,3contains at least one crossing. why? because K3,3 has a cycle ...
4
votes
1answer
42 views

Shortest path problem where edge weight depends on path taken

I am attempting to find the most efficient route to get from a source to a destination in a bus network. Each stop is a vertex in a graph, and each edge between vertices represents a route between ...
-1
votes
1answer
33 views

Scheduling problem on bipartite graph

Consider a bipartite graph $G=(U, V, E)$. Each $v \in V$ represents a soccer team, and each $u \in U$ represents a mini-tournament needs to be scheduled. If $u_i$ and $u_j$ share no common neighbor, ...
2
votes
1answer
79 views

Perfect matching in a graph and complete matching in bipartite graph

When I google for complete matching, first link points to perfect matching on wolfram. It defines perfect matching as follows: A perfect matching of a graph is a matching (i.e., an independent ...
5
votes
3answers
489 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, ...
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 ...
0
votes
1answer
27 views

How does Hassin's algorithm for the Restricted Shortest Path work?

I'm studying the Approximation For Restricted Shortest Path Problem paper and don't understand what he is doing. In particular, I wonder why it is important that one computes upper and lower bounds ...
3
votes
1answer
62 views

Why is Savage's Vertex Cover algorithm a 2-approximation?

Carla. D. Savage formulated the following approximation algorithm for the vertex cover problem. Given graph $G$, start at arbitrary node and traverse $G$ depth-first Obtain DFS tree $T$ ...
-2
votes
1answer
66 views

Dijkstra vs Floyd-Warshall [duplicate]

I know this question is a bit redundant but I am trying to understand a subtle difference between Dijkstra Algorithm and ...
0
votes
0answers
36 views

Vertex-independent paths [duplicate]

Let $s$ and $t$ be 2 vertices (not adjacent) in graph $G$. Let $p_l(s,t;G)$ be the $maximum$ number of vertex-independent paths from $s$ to $t$ in graph $G$, of length $\le$ $l$ ($l \in ...
1
vote
0answers
35 views

How can we add back edges in Ford - Fulkerson algorithm?

I was going through the Ford-Fulkerson(FF) algorithm. The given graph is directed and there is an edge from A to B with capacity y. Now sending a flow of x units (x < y) from A to B is equivalent ...