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)

1
vote
0answers
26 views

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

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
35 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
19 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
59 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
38 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
36 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
49 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
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
2answers
44 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
103 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
85 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
29 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
53 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
16 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
20 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
71 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
120 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
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 ...
1
vote
1answer
39 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
34 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
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 ...
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 ...
6
votes
1answer
49 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
33 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
60 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, ...
1
vote
1answer
56 views

What is the fastest algorithm for finding shortest path in undirected edge-weighted graph?

I am looking for the most efficient algorithm for finding shortest path between two Vertices. The graph is: undirected edge-weighted Non-negative less then 300 nodes I understand that most of ...
2
votes
1answer
75 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 ...
2
votes
1answer
47 views

Algorithm for finding fixed cycles in bipartite graphs in sublinear time

Does there exist an algorithm that will compute in sublinear time whether a bipartite graph contains a cycle of fixed length? For example given a $K_{3,3}$ graph finding if it contains a cycle $C_4$. ...
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 ...
0
votes
0answers
23 views

two connected graph - find linear spanning subgrap such that subgraph is still connected

Graph $G$ is 2-connected. It means that for each two edges there are exists at least to disjont (in terms of edges) paths. Graph $G$ is not directed. Our task is to find spanning subgraph $H$ of ...
1
vote
1answer
52 views

Is HAMPATH in NL/L?

I know HAMPATH is NP complete problem. But is there a way to tell if it is either a NL or L problem? I tried searching a lot of places online but it feels like I am going nowhere. Thanks in advance ...
1
vote
1answer
22 views

What is an efficient algorithm to see if a set of nodes ultimately depend on a certain node in a DAG?

Hopefully this question makes sense. Basically, given a DAG, a set of nodes A, and another node b, I'd like to know if node b is an ancestor of any of the nodes in A in that graph. This is my current ...
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
49 views

Does dijkstra works when I multiply weights of successive nodes

Consider a complete bidirectional weighted graph. Weight of each edge (a,b) is the probability of getting from a to b. So all weights are in range (0,1]. Probability of going from ...