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
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 ...

1
2 3 4 5
80