Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
3,955
questions
0
votes
1answer
27 views
Vertex cover of minimal graph
I'm looking for algorithm that, for given undirected graph $G=(V,E)$, find graph $G'=(V,E')$ with minimal amount of edges that have same vertex cover as G. I mean, vertices $U$ are vertex cover of $G$ ...
0
votes
0answers
12 views
Walks on Directed graphs
Let G = (V,E) be a directed graph, where V is a finite set of nodes, and E ⊆ V × V be the set of (directed) edges (arcs). In particular, we identify a node as the initial node, and a node as the final ...
2
votes
0answers
23 views
Optimal Item Locations given Traversal Paths
I have a given fully-connected undirected graph associated with (known) distances or alternatively a distance matrix, where the nodes or matrix rows/columns represent locations.
Additionally, I have a ...
0
votes
0answers
29 views
Minimum cost bin assignment
I've been trying to solve the below problem the entire day but couldn't come up with a solution. I have the suspicion that it could by solved by a graph algorithm (or maybe some greedy approach?) but ...
3
votes
0answers
36 views
Hardness of an instance of a problem independent of algorithms?
The paper “Where the really hard problems are” (https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf) and others that cite it provide evidence that lots of algorithms for many NP complete problems (...
-1
votes
0answers
32 views
Assignment of Nodes to Multiple Queues
You are given $n$ customers at $n$ nodes and each node is at a variable distance away from all queues. Also each customer is processed in a constant amount of time $c$ when it is in a queue. Assuming ...
1
vote
0answers
15 views
How to efficiently flatten a hierarchical state machine?
David Harel's StateCharts introduces hierarchical states and history mechanism, which are really powerful when modeling complex system behaviour. But when doing model based testing we need a "...
1
vote
2answers
73 views
How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?
I find in many references the fact that if $G$ is a connected planar graph, then for any embedding, $G^{**} \cong G$. However, all those references either say that this fact is trivial, or give the ...
2
votes
0answers
28 views
Relationship between proof and algorithm of Ramsey's Theorem
The following is a problem statement from "Introduction to Theory of Computation" Chapter 0 Problem 0.14:
Let $G$ be a graph. A clique in $G$ is a subgraph in which every
two nodes are ...
1
vote
0answers
168 views
Total running time expressed in O notation of a word ladder program all words same length
I am trying to figure out a big O expression for the running time given $V,E,F$ for a word ladder or word chain program that I have written in Java. I am using undirected graphs with BFS.
What is ...
0
votes
1answer
15 views
Alternatives for finding sources in a DAG
I have a hard time seeing what the alternative approach is in linearizing a directed acyclic graph (DAG). Chapter 3 of Algorithms by Dasgupta et al. states:
Property Every dag has at least one source ...
0
votes
1answer
20 views
How to simulate online matching algorithms (implementation)
I was reading about online algorithms and bipartite matching.
I found an implementation that works fine on several websites (like geeksforgeeks).
For the online version, I found this paper
https://...
1
vote
1answer
37 views
Concrete example of an admissible A* heuristic compared to Djisktra
As I understand it, A* is a general form of Djikstra where the selection of the next node to visit can be based on something other than the actual distance. For example, with Djikstra, you'd use a ...
2
votes
2answers
54 views
Find cycles with specific weights in complete graph
(this is a cross-post from mathoverflow)
Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight)....
0
votes
1answer
34 views
Create Shortest Path tree for every node after Floyd Warshall in O(nm)
Right now I am stuck with the problem, how all shortest path trees can be created in O(n*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after ...
0
votes
0answers
13 views
Looking for a evolution/timeline algorithm
I am trying to draw a presentable timeline and I am doing some research about available algorithms
al
Here are the timelines of interest
I already found a great article by Bill Mill Drawing ...
5
votes
0answers
77 views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
0
votes
1answer
30 views
Isn't an improper subset of edges of a cyclic graph, cyclic and thus not a minimum spanning tree?
This is the formal definition of a minimum spanning tree taken from Algorithms by Dasgupta, Papadimitrious and U. Vazirani.
Input: An undirected graph $G = (V,E)$; edge weights $w_e$.
Output: A tree $...
1
vote
1answer
47 views
Graph add at most 2 edges to make all graph nodes degree even
Given an undirected graph that is represented by its adjacency matrix, return whether or not is it possible to add no more than two edges to this graph in order to make all the degrees of nodes even. ...
1
vote
2answers
35 views
Maximum matching for general graph
I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must ...
0
votes
1answer
11 views
Finding shortest path for DAG using dynamic programming vs topological sort?
Why is it that when I read about finding the shortest path for a DAG I usually just hear about topological sort? Why not use dynamic programming where the shortest path to a vertex is simply the ...
1
vote
1answer
9 views
What is the complexity class of finding vertex cover number of a simple graph?
Suppose we have a simple graph $G$. We know that finding the minimum vertex covering set for $G$ is in the NP-hard class. But, what about the complexity class of finding the size of the set, i.e., the ...
1
vote
2answers
39 views
Selecting connected subgraph that exceeds value c, with least possible weight
Given a graph $G$ where each node has a value $c$ and weight $w$, I want to select a connected subgraph $V^*$, such that,
Sum of all values in $V^*$ crosses threshold $t$.
Sum of all weights(say $w^*...
1
vote
1answer
8 views
Is it possible to compute the minimum vertex covering set in quasi-polynomial time, by knowing the vertex cover number?
If we know the vertex cover number for a simple graph $G$ denoted by $\tau(G)$, is it possible to find the minimum vertex cover set for $G$ in quasi-polynomial time? As I found, we cannot find any ...
1
vote
0answers
22 views
Finding s-t min-cut of undirected graph
Given an undirected graph with non-negative edge weights, and two vertices $s,t$ in the graph. I would like to find the minimal cut such that $s$ and $t$ are on different sides of the cut.
For example ...
1
vote
0answers
28 views
Equivalence of two approximation algorithms for min Steiner tree
I learned two approximation algorithms for the min Steiner tree:
The first algorithm:
1- Compute the metric closure G' of G.
2- Compute a min spanning tree T' of G'
3- Construct the union U of the ...
0
votes
0answers
78 views
Devise Mont Carlo and Las Vegas Algorithms to Solve Maximum Independent Set
I am trying to devise a Las Vegas algorithm to solve Maximum Independent Set, but I don't know how to start.
Also, I want to devise a Mont Carlo algorithm for this problem.
I would appreciate any help....
-1
votes
0answers
35 views
Finding a Spanning Tree Using other Spanning Trees of $G=(V,E)$
I am having trouble coming up with a polynomial time algorithm to solve the following problem:
Let $𝐺=(𝑉,𝐸)$ be an undirected and unweighted graph with $𝑛$ vertices. Let $𝑇_1,𝑇_2,...,𝑇_𝑘$ be $�...
1
vote
1answer
28 views
“Equality” problem in distributed computation
I recently started learning about distributed computation on graphs (not to be confused with parallel computation with threads).
I have seen as a side note in a few lower bound proofs, a reference ...
-4
votes
1answer
31 views
Finding a clique in undirected graph is P or NP? (proof) [duplicate]
Finding a clique $C$ in an undirected graph $G= (V, E)$ such that $|C| > |V|/2$ is in P or NP-hard? How can I prove it?
2
votes
1answer
30 views
Generating sparse connected Erdős–Rényi random graphs
Given a random graph $G(n, p)$, where $n$ is the number of nodes and $p$ is the probability of connecting any two edges, it is known that $t = \frac{\ln(n)}{n}$ is a threshold for the connectedness of ...
0
votes
0answers
27 views
Cycles of a multigraph with a property on the edges
Let $n$ be a positive integer. On a circle are arranged $n$ points $A_1$, $\ldots$, $A_n$. We put some arrows from $A_1$ to $A_2$, from $A_2$ to $A_3$, etc., from $A_n$ to $A_1$. On each arrow are ...
0
votes
1answer
12 views
How does BFS guarantee the minimum path for this problem?
https://leetcode.com/problems/bus-routes/
You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.
For ...
3
votes
1answer
73 views
Completing tasks on a graph
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. The graph $G$ is complete, which means we can traverse $(i, j)$ for all $i, j \in V$. At each vertex $v \in V$, there is a task that ...
1
vote
0answers
26 views
Binary ↔ Gray permutation matrix
Generating a Gray code representation of a binary number can be thought of as mapping one binary number onto another binary number. Therefore, $n$-bit Gray code is a permutation of $2^n$ elements.
...
4
votes
1answer
38 views
Further papers or code on SMA*+?
I'm interested in the Lovinger and Zhang paper Enhanced Simplified Memory-bounded A Star (SMA*+). Are there any further papers on this algorithm or publicly-visible code (in any language) ...
1
vote
0answers
26 views
Dijkstra's algorithm - additional properties
Say we let $R$ denote the set of currently chosen vertices in Dijkstra's algorithm, $d$ be the currently stored path-length estimates, and $s$ be the source. The standard property that we know is true ...
0
votes
0answers
19 views
Software for triangulation flip graphs?
I need to generate flip graphs on around 10 points (more would be nice). Specifically, I would like flip graphs on subsets of the integer lattice, so the coordinates of each point are integers. Is ...
2
votes
2answers
122 views
Shortest path including all nodes in a subset
Given a directed graph $G=(V, E)$, two nodes $s, t \in V$ and a subset of nodes $U \subseteq V$.
Provide an algorithm that determines if there is a shortest path from $s$ to $t$ that passes via all ...
2
votes
0answers
90 views
Detecting cycles with weight zero in a directed graph
I am given a directed graph $G=(V, E)$ with a weight function $w: E\to\mathbb{R}$, that doesn't contain negative cycles.
I need to find an algorithm that returns ...
1
vote
0answers
34 views
What does “yields” mean in the phrase *yields no back edges* in DFS?
What does yields mean in the phrase yields no back edges in the context of DFS?
...
1
vote
1answer
62 views
Triangles covering all vertices of a tri-partite graph
This question is an extension of this one: Min path cover for a three-layer graph with all paths traversing all layers.
I'm designing fictional fruits. Each fruit has three attributes; color, taste ...
1
vote
1answer
83 views
What does Dijkstra's algorithm become, when you replace path cost with edge cost?
Consider a variant of Dijkstra's algorithm (for a directed graph) where nodes are visited not in order of total path cost, but in order of incoming edge cost. (Assume here that all edge costs are ...
0
votes
0answers
18 views
How to find diffrenet ways to implement merge and delete_min operation in binomial heap?
I have searched on the internet to find different ways to learn binomial heap operations. What I have found is not quite helpful for me.For example, for delete min operation the algorithm says:
...
2
votes
1answer
39 views
Find the set of all edges which there is a cycle such that for every $e' \in C, e'\neq e$ : $w(e')\leq w(e)$
Given an undirected graph $G=(V,E)$ and weight function: $ w: E \rightarrow \{1,2,...,10\}$.
Describe an algorithm that finds the set of all edges $e\in E$ for which there is a cycle $C$ in $G$ that ...
1
vote
2answers
29 views
Given a list of vertices in a binary tree output minimal sublist with the same lowest common ancestor
The input: a binary tree and a list $L$ of vertices in that tree.
The output: a sublist of $L$ of minimal length that has the same lowest common ancestor as $L$. If there is several sublists of ...
2
votes
0answers
29 views
find zero weight cycles in a directed graph [duplicate]
I need to plan an algorithm that decides if a directed weighted graph $G = (V,E)$ has a zero weight cycle.
the graph has no negtive cycles
the algorithm needs to be in $O(|V| \cdot |E|)$ time
my ...
3
votes
1answer
43 views
A question about the work per recursive call in FPT vertex cover of size k algorithm
I have been looking at the FPT(Fixed Parameter) algorithm for checking if a vertex cover of size k exists.The algorithm goes as follows:
VertexCoverFPT$(G, k)$
if $G$ has no edges then return true
if $...
2
votes
1answer
47 views
Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time
I am looking for an algorithm for approximating the chromatic number of an undirected simple graph with $n$ vertices in $O(n^{c_1})$ time and $O(n^{c_2})$ space, for some constants $c_1$ and $c_2$. ...
2
votes
1answer
43 views
How to avoid monochromatic cycles?
I am working on the following exercise:
Consider a simple and connected undirected graph $G(V,E)$. Show that one can colour the edges of $G$ in polynomial time and with as few colours as possible ...
