Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

learn more… | top users | synonyms (1)

0
votes
1answer
11 views

Single-source shortest paths as a linear program

I saw that I can formulate single-source shortest path as the following linear program: Given $G=(V,E)$ $w:E->R$ and no negative cycles: $max$ $d(s,t) $ s.t $\forall (u,v)\in E :$ $d(s,v) \le ...
3
votes
0answers
14 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
20 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 ...
-1
votes
0answers
51 views

Deletion of a key edge on a flow network [on hold]

A key edge is defined to be an edge whose deletion causes the largest drop in maximum flow. I have a few questions about key edges. 1) Does a key edge always have the largest capacity of all the ...
0
votes
1answer
47 views

Longest path in a graph with special property

I have a special graph in which I have two types of edges only, say one with type 0 and one with type 1. Now I have to find a longest path in the graph such that it starts with a vertex then follows ...
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. ...
0
votes
0answers
10 views

Finding an invalid walk order between two nodes when edges have traversal limits

Given an arbitrary connected graph with a start and goal node, with both directed and undirected edges, where each edge has a maximum number of times it may be traversed during a single traversal (at ...
-1
votes
0answers
14 views

How many changes require in tree decomposition of a graph when adding a new edge to graph?

How many changes require in tree decomposition of a graph when adding a new edge to graph? Let $G(V,E)$ be a graph with constant treewidth $K$. we add a new edge to graph ( we khow if $u,V $ be in ...
1
vote
1answer
23 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 ...
1
vote
0answers
33 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
0answers
37 views

Viterbi algorithm for shortest path calculation

I have to write an essay about shortest path calculation with Viterbi algorithm. Since I am interested in finding the path with the least weight on the network graph, I am a little bit confused how to ...
0
votes
0answers
40 views

How can I tell if my edge is border or interior?

I have an arbitrary collection of nodes connected by edges. I am trying to find a good way to tell if an edge/vertex is on the border or not. The red nodes and blue lines are considered on border. ...
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 ...
4
votes
0answers
76 views

Maximum Number of Edge Disjoint Paths of Length k in DAG

Is it known if the problem of finding the maximum number of edge disjoint paths of length k in a DAG is in P? Or has it shown to be NP-Complete? If so, are there approximation algorithms known for it? ...
0
votes
1answer
40 views

Graph “coloring” problem minimal number, each edge has a colored end

(there is the possibility that the answer to my question is "Traveling Salesman, dude!". If that is the case, Please just say so and I'll try it again on my own using Traveling Salesman. We have not ...
2
votes
1answer
40 views

Count the number of Euler PATHs in directed graph?

I would like to find all Euler PATHs in a directed graph. Counting (instead of finding) all the Euler PATHs is sufficient. Circuits are not good for me, only Paths. I am doing a problem, that I ...
3
votes
1answer
12 views

Informed search with a lower-bound heuristic?

I am well aware of informed graph / tree search strategies for optimal solutions when one has an admissible heuristic - i.e. one that never overestimates the minimum cost from a node to any goal ...
0
votes
0answers
28 views

Graph algorithms for vulnerability and optimality of network

I am studying a research paper which is concerned with finding paths from a source nodes to a single sink node keeping in mind 2 things. 1.The security of the path. 2.The optimality of the path. ...
0
votes
1answer
51 views

What is wrong with my LP exercise (longest path cost for a graph)

I have to do a linear programming exercise but i have some problems regarding the result. I have a graph with N nodes and E edges, that is not acyclic, and each edge is associated to a cost. I have ...
0
votes
0answers
25 views

Search maximal matching in a non-bipartite graph

Given a G(V,E) graph and we want find a maximal matching. If it is a bipartite graph, there is the Hungarian method can solve this problem. But how can I solve the problem if it is a non-bipartite ...
1
vote
2answers
30 views

Reconstruction of drawing sequence from video

I have a video that record the drawing sequence with a pencil by a painter. I want to reconstruction the sequence from the video. And I have google some keywords like "drawing sequence ...
3
votes
1answer
35 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
2answers
56 views

How does DFS produce MST and All pairs shortest paths in unweighted graphs?

I was reading Application of DFS from here where I came to a statement which I cannot really understand. Would anybody mind explaining this to me. For an unweighted graph, DFS traversal of the ...
0
votes
0answers
55 views

DAG, search for cheapest descendants with same color

Let $G=(V,E)$ be a DAG. For each $v\in V$ you have a color $c(v): V \rightarrow \left\{c_1 \ldots c_k \right\}$ where $k$ is a fixed number, and a weight $p(v)$. For every $v \in V$ you have to find ...
4
votes
1answer
42 views

Determining if an undirected connected graph is minimally connected

I'm trying to solve a practice problem in Elements of Programming Interviews (19.4) and I am a bit confused. The question is to determine if an undirected connected graph is minimally connected. ...
0
votes
0answers
9 views

Proving the Multiway cut problem is NP Complete [duplicate]

Problem Statement: Given k nodes: $$ u_1, u_2, u_3..., u_k $$ remove edges of total minimum weight that separates $u_i$ from $u_j$ for all $i != j$ for all k >= 3 I just need some help identifying ...
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 ...
1
vote
0answers
36 views

Choosing edges to disconnect graph

I have an undirected simple graph and an integer x. My goal is to remove x edges from the graph so the largest connected component of the graph after the removal will be minimal. I tried to think how ...
1
vote
0answers
13 views

Inequalities in a multicommodity min-cut max-flow theorem

I am reading this classic paper by Klein, Plotkin and Rao titled Excluded Minors, Network Decomposition and Multicommodity Flow. In section 3, Theorem 3.1, they define $\hat \ell(vw) = \lceil ...
4
votes
1answer
109 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 ...
1
vote
0answers
91 views

Finding optimal element with two criteria

Let there be a (unsymmetric, directed, weighted) graph ( $\mathbb{G}$, capacity $m$ ) and an array ( $\mathbb{A}$, fixed capacity $n$) of objects ($m>>n$). The array contains references to a ...
3
votes
1answer
30 views

How to find the shortest path from some vertex in set $S$ to set $S'$

If i have a graph $G=(V,E)$, a subset of vertices $S \subset V$ and a second set of vertices $S' \subset (V\setminus S)$, what is the best way to find the shortest path connecting the two sets? Here ...
5
votes
1answer
94 views

Shortest path in a known room for a Roomba

I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search ...
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 ...
3
votes
0answers
17 views

Similarity-based binary representation of graph

I have given an undirected graph of which I want to associate every vertex with a (random) binary vector. I can chose the dimensionality of the vector but it has to be identical for every vertex. The ...
4
votes
1answer
37 views

Expected number of common edges for a given tree with any other tree

So I am working on a problem where I have a set of (labeled) nodes and I have a tree structure (rooted) over that set of nodes. The goal for me is to automatically generate that tree structure. To ...
1
vote
0answers
22 views

Minimum feedback vertex set [closed]

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $Η$ is the current graph, until there are no more cycles left.What ...
2
votes
1answer
72 views

Algorithm to find the shortest walk with k leaf nodes on a tree

Let's say I have a general tree. What algorithm can I use to find a shortest walk that starts at the root, passes through exactly $k$ different leaves, and ends at the root? Passing through a ...
3
votes
1answer
96 views

Maximum bipartite matching with extra reward for covering certain sets

Consider the following variation of Bipartite Maximum Matching. As usual, we have a bipartite graph $G$. In addition, there is an additional collection of sets $S_1,S_2,\dots,S_k$, with each set ...
3
votes
3answers
121 views

Algorithm to find shortest lightest path in a graph from source

Given a directed graph $ G = (V,E)$ with non-negative(zero and positive) weights on the edges, and a vertex $ s \in V $ Problem: Find the lightest path from $s $ to each and every vertex $v \in V$ ...
2
votes
1answer
126 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 ...
1
vote
1answer
41 views

Check if given vertices form a connected subtree in a graph

The approach described in this question is wrong. It'll find false positives for disconnected components with multiple vertices. See D.W.'s answer for a reliable alternative. This might be a simple ...
1
vote
1answer
35 views

Find a source-sink-path that touches a subset of edges

I have a directed graph that has a source node and a sink node and a subset of marked edges. I need to find a path from source to sink that contains at least one marked edge and is cycle-free.
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 ...
4
votes
1answer
37 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 ...
6
votes
1answer
50 views

Algorithms on random geometric graphs

A random geometric graph (https://en.wikipedia.org/wiki/Random_geometric_graph) is constructed by choosing $n$ points in $\mathbb{R}^d$ at random according to some distribution, and setting $p_i \sim ...
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 ...
1
vote
1answer
62 views

Algorithm A vs Algorithm A*: What's the difference?

I can find quite a bit of literature on A* but very little on A. What is the difference between the two search algorithms?
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, ...