Questions tagged [graphs]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
12 views

Maximum planar subgraph problem

Given a graph G I want to find the maximum planar subgraph which is a grid graph. (Because the nodes of this subgraph represent points on a grid). Is there any library in python for finding the ...
1
vote
0answers
17 views

Warnsdorff's rule: more errors with odd sized boards

I wrote an algorithm based on the Warnsdorff's rule to solve the knight's tour problem, where you need to create a sequence of moves of a knight on a chessboard such that the knight visits every ...
0
votes
0answers
39 views

Can this special case of Set Cover problem be solved in polynomial time?

Let $U$ be the set of elements and $S$ be the subset collections. There exists a tree $T$ that each node is corresponding to an element in $U$. And for every subset $s$ in $S$, $V(T) \bigcap s $ is a ...
1
vote
1answer
143 views

Algorithmic Problem on Trees

Given a directed, rooted tree with $n$ vertices, the height of a vertex $v$, $h[v]$ is the number of edges on the longest path from $v$ to some reachable leaf node. Give an efficient algorithm to find ...
1
vote
0answers
24 views

Cluster 3d points with constraints

I have some 3d point cloud I wish to cluster into some number of clusters. I have the probability of two points being in the same cluster given as some function of their relative locations, with the ...
8
votes
11answers
3k views

Real life examples of *zero* weight edges in graphs

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously. Yet, when I recently read here a question on real life example ...
1
vote
0answers
26 views

Proof that every vertex in the same strongly connected component of a graph $G$ happen to appear in the same DFS tree

My Professor proved that every vertex in the same strongly connected component of a graph $G$ happen to appear in the same DFS tree (which is also called tree of predecessors). He proved it by ...
-1
votes
0answers
31 views

Where are the region adjacency graph algorithms?

I am interested in the Region Adjacency Graph construction problem in the context of (labelled) digital images. I am surprised to find very few resources on the topic, with the notable exception of a ...
2
votes
0answers
24 views

Why is $O(nk)$ an upper bound for the $k$-gossip problem?

I am studying the $k$-gossip problem on dynamic graphs against an adaptive adversary. Essentially, we are given a set of tokens $\mathcal{T}$ which are distributed amongst the nodes such that each ...
3
votes
1answer
45 views

Shortest possible path between closest pair of specific nodes in a maze

Need to find the shortest distance between the closest pair of 'r' and 'b' nodes. You can traverse along '.' elements, but not 'o' elements. How can we do this in $O(MN)$ time? (M rows, N cols). $O(...
0
votes
0answers
20 views

Minimum spanning tree containing specific edges

Given a weighted undirected graph and a list of edges (without cycles), how can I create an MST that contains all those edges (or says that such an MST does not exist)?
6
votes
1answer
171 views
+50

Fast and compact data structure for dynamic graphs

A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ may be represented in central memory as follows: an associative array (hash table) $V$ gives for any $v\in \mathcal{V}$ the list of its neighbors $V[v]$...
18
votes
6answers
3k views

Real life examples of negative weight edges in graphs

I am unable to relate to any real life examples of negative weight edges in graphs. Distances between cities cannot be negative. Time taken to travel from one point to another cannot be negative. ...
2
votes
1answer
30 views

What Graph Algorithm can determine ideal distribution of items to travel the least amount of distance from any node?

I have a problem that's been bugging me, but I'm not sure what algorithm can solve it. Alice has medicine that she needs to use as quickly as possible in case of an allergy attack. She wants to ...
2
votes
0answers
17 views

UCYCLE in LOGSPACE and linear time

Consider UCYCLE, the problem of recognizing undirected graphs containing a cycle. On the one hand, it's in LOGSPACE, see this stackexchange thread: start at every vertex $v$ a DFS and check whether it ...
1
vote
0answers
15 views

Do the Prim’s algorithm and the Kruskal’s algorithm always obtain the same minimum spanning tree (MST) on a given input graph? [duplicate]

Do the Prim’s algorithm and the Kruskal’s algorithm always obtain the same minimum spanning tree (MST) on a given input graph? I have tried drawing a bunch of graphs with non-unique edges and ...
10
votes
2answers
1k views

Find shortest path between two vertices that uses at most one negative edge

Given a directed graph $G = \langle V,E \rangle$ with $n$ vertices and $m$ edges and a weight function $w:E \rightarrow \mathbb{R}$, together with two vertices $s$ and $t$ in $V$: Describe an ...
0
votes
1answer
41 views

modify dfs to find longest path

Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$. For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that ...
0
votes
1answer
68 views

How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time

This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani. Specifically, the problem statement is: Give a linear-time algorithm that ...
0
votes
1answer
21 views

Maximal edge weight clique of given size

Let $G$ be an undirected fully connected weighted graph with $N=|V|$ vertices. Given $M<N$ we wish to choose $M$ vertices such that the sum of weights between the chosen vertices is maximal, i.e. ...
0
votes
1answer
57 views

Shortest walk from $u$ to $v$ through $w$

We have an undirected, weighted graph $G=(V, E)$ with two weight functions $W_1 : E \rightarrow \mathbb{R}^{+}$ and $W_2 : E \rightarrow \mathbb{R}^{+}$ such that for every $e \in E$ we have $W_1(e) &...
-1
votes
0answers
18 views

Control Flow Graph - How to represent returns in code

Consider the following program int someCode1(int x){ if (x < 0) return 0; else return x; Last Statement;} Last statement could be either "printf(...
1
vote
1answer
55 views

There are n cities and m possible bidirectional roads and k temple. build roads with minimum cost such that each city has access to at least 1 temple

There are n cities and m possible roads and k temples. The cost of each road is given. Build ...
3
votes
0answers
64 views

Deciding whether a given flow is unique in $O(\lvert V \rvert + \lvert E \rvert)$ time

I am stuck with the following exercise: Is it possible to decide whether a given flow $f$ is a unique mamimum flow in $O(\lvert V \rvert + \lvert E \rvert)$ time? I am not sure that this is possible....
0
votes
0answers
20 views

Partition a graph into subgraphs such that a partition contains up to X number of a particular node type

I have a DAG graph which contains two types of nodes, A and B. I am looking for a graph partitioning algorithm that can partition a graph in sub-graphs such that each sub-graph contains up to X number ...
1
vote
2answers
31 views

Resolving a dependency graph with insufficient resources to store all states

A common way to resolve a dependency graph is to compute an execution order, and then execute each stage in turn - storing and fetching the resources as necessary. In this example, when executing ...
1
vote
1answer
56 views

Algorithm to find shortest distance from source to all other vertices of graph in O(m)?

My question is for (c), as I struggle to find an algorithm that can do this in O(m) time.
0
votes
1answer
124 views

Maximum flow on a n ×n grid

I am currently dealing with a network flow problem and I am trying to find some similar solved problems to help me formulate my solution. The text is: You are the owner of a large chain of franchise ...
0
votes
1answer
55 views

How can it be proved that two different kinds of dfs unequivocally define a unique tree?

How can it be proved that two different kinds of dfs ( for example let call them inorder and postorder) unequivocally define a ...
2
votes
1answer
39 views

Minimum vertices to remove from a graph so that no path exists between two given vertices anymore

Given an undirected graph $G=\{V, E\}$ with its vertices numbered from $1$ to $V$, given two vertices $s$ and $t$ $(1 \leq s \lt t \leq V)$, what is the minimum number of vertices (except $s$ and/or $...
1
vote
0answers
40 views

Shortest path as a linear program

I just encountered this formulation of the shortest $s$-$t$ path problem as a linear program in a homework. I don't understand exactly the meaning of the variables and restrictions. Here, $G = (V, E)$ ...
2
votes
1answer
77 views

Prove finding a spanning tree with no more than 50 leaves is NP-hard

This is a homework question. Consider the problem of finding if an undirected graph $G$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard? I think it is and I'm trying to ...
2
votes
1answer
37 views

Find all combinations of adjacent records matching a graph template

I have a graph theory or combinatorics problem that probably has a solution, but I haven't been able to find it. The problem can be simple: in the second figure below, choose one yellow block from ...
6
votes
3answers
1k views

Does the Minimum Spanning Tree include the TWO lowest cost edges?

Wikipedia's Minimum Spanning Tree reads: Minimum-cost edge If the minimum cost edge e of a graph is unique, then this edge is included in any MST. Proof: if e was not included in the MST, removing ...
3
votes
0answers
52 views

Graph coloring problem with violations

I would like a name for the following problem. We consider a relaxed vertex coloring problem, where Let $k$ be the number of colors Let $B$ be the set of edges violating coloring, i.e., $$B := \{(u,...
0
votes
1answer
27 views

Pure Directed Graph

How can a directed graph be efficiently represented in a purely functional language like Haskell? Could someone suggest relevant materials on this topic? (functional pearls perhaps?) Thanks.
3
votes
0answers
47 views

Cost of finding optimal elimination order in a planar tensor network?

Suppose we are computing a sum over $n$ factors which can be represented as a planar tensor network. What is the complexity of finding an optimal elimination order? For example, take the following ...
1
vote
1answer
20 views

Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?

Let suppose we order the nodes first by degree (in + out), to get a list of node structures: ...
1
vote
1answer
43 views

Is the MCP language really np hard?

I have a graph $G=\left(V , E\right)$ and source $s$ and target $t$. I also have a weight function $w: V\rightarrow \mathbb{R^+}^k$, meaning a vertex given $k$ non negative weights. There is an upper ...
1
vote
0answers
28 views

Building a Graph with adjacency list of Positions from Grid [closed]

I am attempting to build a Graph with adjacency list. I am using Microsoft.Xna.Framework; and I can use Point(x,y) class from it....
0
votes
0answers
42 views

Finding the shortest path with this algorithm

This is a homework question. We want to find the shortest $s$-$t$ path in an undirected weighted graph $G = (V, E)$ with capacities $c_e$ for each edge and positive weights. Let $S'$ be the set of all ...
2
votes
1answer
61 views

Restore planar graph from vertex degrees

Suppose you are given a list of vertices (with known positions) and their respective degrees, find any set of non-intersecting edges that satisfies the vertex degrees. Or, in other words, connect the ...
-1
votes
1answer
26 views

Given the hypercube Q3 of 8 vertices, what is x + 10y where x is the minimum vertex cover set size and y is the maximum independent set size?

Sorry for the shoddy formatting in the title, here's something clearer: Given the hypercube Q3 of 8 vertices, what is x + 10y where x is the minimum vertex cover set size and y is the maximum ...
0
votes
0answers
39 views

How to solve min cost perfect matching problems?

I'm trying to design an algorithm for the following generalized assignment problem. We converted the problem to a weighted bipartite graph constituted of two sets $A$ and $B$ where $|A| \ne |B|$. Any ...
1
vote
1answer
52 views

Why are there here at most $ \vartriangle \cdot E $ paths?

I ran across this proof from the following paper: Finding and Counting Given Length Cycles But I do not understand the third line. There are at most $ \vartriangle \cdot E $ such paths and they can ...
-2
votes
1answer
58 views

Find nodes at k distance from given source node in an undirected cyclic graph if k<=1e9

I have encountered this problem many times. In an undirected graph, you need to get all the nodes/one node that is k distance away from the given source node (...
0
votes
0answers
15 views

Algorithms for generating graphs with different global and local topology

I want to generate different kinds of graphs with different topological properties. I am interested in modeling the global structure as well as the local structure. That is, I not only want to ...
0
votes
0answers
21 views

Minimise vertex loss converting DCG to DAG

I have a DCG that I want to lay out with the parents on the left and children to the right. I want to maximise the number of all children present to the right of all parents whilst minimising the ...
3
votes
1answer
24 views

On a coloring that uses $2\cdot a\left( G \right)$ colors

Denote $G=\left( V, E \right)$ arboricity by $a\left( G \right)$. I'm trying to understand why $G$ is $2\cdot a \left( G \right)$-colorable. I came across this post. Both the OP and the answer say ...

1
2 3 4 5
87