Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
1
vote
1answer
15 views
Is there any implementation of AO* algorithm?
I'm trying to solve And-Or Graph, and I find AO* algorithm can handle it. Someone said it's already used in AI, but I can't find it in detail.
Have it implemented? Or it's just a pseudocode that can'...
2
votes
1answer
26 views
Proving NP hardness about graph creation problem with triangle number
I have graph creation problem.
Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in ...
1
vote
1answer
38 views
Reducing a graph without changing its chromatic number
Does reducing a graph (removing or replacing vertices or edges) without changing its chromatic number has a specific name?
Take this cactus graph as an example (although my question is about an ...
1
vote
2answers
42 views
Either find a perfect matching, or return a witness that none exist [duplicate]
I am looking for a polynomial-time algorithm that takes as input a bipartite graph $(X\cup Y, E)$, and returns one of two options:
If a perfect matching exists, it returns the matching;
Otherwise, it ...
0
votes
2answers
19 views
calculation of Transitive Closure
This question is not from homework, but rather as preparation for the test:
The calculation of place-in is a calculation in which the algorithm does not need space beyond the output size (beyond
...
1
vote
1answer
38 views
How to perform local search to find maximal induced subgraphs?
I'm looking for efficient ways to perform local search to find maximal induced subgraphs that satisfy certain properties : a tree, a forest or a bipartite subgraph for example.
What I mean by local ...
0
votes
0answers
17 views
Finding disjoint paths between any number of cell pair marked in nXn matrix
What should be algorithm to find all the disjoint paths between any number of pairs of cells given in matrix?
We will say two paths will not intersect if there there is no cell common between any two ...
0
votes
0answers
7 views
Finding all possible exclusive cliques in a graph
TL;DR I need to find all possible ways to traverse an undirected cyclic, possibly disconnected graph to find all exclusive sets of connected nodes which satisfy certain criteria.
There's a graph of ...
0
votes
1answer
14 views
Removing max number of edges while keeping minimum distances
Suppose we have a graph with vertices from 1 to n.The graph is undirected and the starting point is 1 and we have path from 1 to any other vertex.We also have positive weight on each edge and there ...
2
votes
1answer
32 views
Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?
For the proof of a maximum of (n 2) min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.
...
0
votes
0answers
15 views
How to sort a woven shuffled stack
Say you have sort of a "woven shuffling situation" going on, sort of like this.
Or that just looks like a regular shuffle for the most part. I'm trying to show the situation where something can be ...
0
votes
0answers
11 views
How to identify the final set of “contours” when combining multiple primitive contours
This problem is in relation to how fonts work. Say you have a "glyph" that is composed of of these 5 "contours", or enclosed loops.
On their own, each of them is a unified whole. The easiest thing we ...
2
votes
1answer
62 views
Confused about the correctness proof of Dijkstra's algorithm
In the proof of the correctness of Dijkstra algorithm, there is a lemma stating as follow:
Let u be v's predecessor on a shortest path P:s->...->u->v from s to
v. Then, If d(u) = δ(s,u) and edge (...
0
votes
0answers
35 views
Show that if the transitive closure can be computed in T(|V |) time then BMM can be solved in O(T(3n)) time
Show that if the transitive closure can be computed in T(|V |) time then
BMM can be solved in O(T(3n)) time.
I didn't understand the proof in the context of building edges. I added the proof
i tried ...
0
votes
1answer
35 views
Quick and space-efficient way to find whether two sets intersect
I hope you can help me -
Given a lot of sets containing integers,
I'd like for any two sets, to quickly (i.e. O(1)) ask whether they intersect.
Note that I don'...
3
votes
1answer
102 views
Optimal dividing of K people into N groups
A teacher at a school has to do this on a regular basis. Let's say 12 students should be divided into either 4 groups of 3, or ...
0
votes
1answer
30 views
Max Weight Path in a Graph
I know that this problem is a known NP-Complete problem, but I'm curious as to why a particular algorithm won't work. Given a graph $G = (V,E)$, and edge weights $w(e)$, why can we not create a new ...
0
votes
0answers
31 views
Can the Chinese Postman Problem be solved with the Traveling Salesman Problem?
Multiple people suggest that the Chinese Postman Problem (also referred to as the Route Inspection Problem) of a graph G can be solved by applying the Traveling Salesman Problem to its line graph L(G)....
3
votes
2answers
47 views
When searching graphs breadth-first and depth-first color the graph. Who un-colors the graph when the search is completed?
The depth-first and breadth-first algorithms for traversing graphs use a flag (or color) to mark nodes when they are visited. For example some forms of the algorithms use white/grey/black as colors. ...
1
vote
1answer
40 views
find all paths from source to destinations and then calculate the path with minimum cost
I am trying to solve one problem. Please refer complete problem statement before proceeding.
You are given a road network, with N cities and M bi-directional
roads. Each road has some positive ...
1
vote
1answer
29 views
Delete a node with 2 children in a binary search tree
Recently in class we learned how to delete a node from a binary search tree. Since in a binary search tree, each node can have at most 2 nodes, there are 3 cases of deletion.
Case 1: The node is a ...
0
votes
1answer
25 views
Increasing the weights of all edges in an undirected graph makes a minimum cut still minimum
We have an undirected graph, with a weight function and a minimum cut. If you raise the weights of all the edges by one, the minimum cut remains minimal even with the new weights.
I know this is ...
0
votes
0answers
19 views
Are there any formal grammars describing the set of all directed graphs?
Let GRAPHS be the set of all directed graphs.
Is there a set of strings STRYNGS such that there exists a bijection ...
2
votes
1answer
29 views
Can the Dijkstra algorithm work with a negative arc?
When there is no negative circle in the graph?
And can Dijkstra not work even if there is a negative arc that does not create a negative cycle?
3
votes
0answers
171 views
How to select a loop nesting trees for irreducible loops?
I am trying to understand the process of analyzing a control flow graph and building a tree of loops, both reducible (single entrypoint) and irreducible (multiple entrypoint), using the algorithm ...
1
vote
0answers
65 views
Decomposition of a bipartite graph into complete bipartite graphs by adding the smallest number of edges
A bipartite graph $G$ and an integer $K$ is given. I want to decompose $G$ into $K$ complete bipartite graphs by adding the smallest number of edges.
Below is an example of decomposition when $K=2$. ...
1
vote
1answer
28 views
What's the usage of $S$ in Dijkstra shortest path algorithm in the book Introduction to Algorithms?
I don't understand how the $S$ is needed in dijkstra shortest path algorithm. For each node $v$ in $G.V$, the $v.\pi = previous\_node$ is used to denote it previous node in the shortest path to the ...
1
vote
1answer
16 views
Will MST find the shortest path for each pair $(r,v)$?
Will local best choice will lead to global best choice? In other words, I'm thinking about whether it's possible that the MST has to put its branch location in the middle of two far nodes ...
0
votes
0answers
8 views
What is the algorithm behind Strava's “Fly-bys” feature?
Strava's Flyby feature enables users to see who they passed on runs and rides.
From the strava website:
Flyby is a Strava Labs tool that lets you playback your activity, as well as those near you, ...
0
votes
2answers
30 views
Algorithm to explore every node in a graph
I need an algorithm to explore every node in a graph (starting at any given node). Each node can have multiple parent nodes and multiple child nodes.
The following algorithm (in psuedocode) appears ...
5
votes
1answer
87 views
Why is Adleman's molecular algorithm for Hamiltonian Path linear?
In Adleman's 1994 paper (archived), he describes a method of manipulating DNA molecules in a lab that results in a solution to the Hamiltonian Path problem with high probability.
He claims that "The ...
1
vote
0answers
19 views
How to find how many times an object's path crosses another?
I have several hundred objects that will move in a fixed area throughout the day. Frequently the objects will cross over another object's path, either at the same time (eg. a collision) or within a ...
2
votes
1answer
38 views
Algorithm to find sets of vertices connected to at most one incoming and one outgoing vertex outside the set
I have a directed graph with vertices $V$, and I need to find a strict subset $U$ of its vertices such that:
$U$ contains at least two vertices, and $U \neq V$
There is at most one vertex in $V \...
1
vote
1answer
30 views
Generating a random minimum spanning tree
I am tring to find the simplest method of generating a random minimum spanning tree.
My intention is to randomly generate a Level in a game where there are n amount of fixed sized rooms existing on a ...
1
vote
1answer
32 views
Polynomial time algorithm - Matching pairs of vertices
Let T be a tree with root r and S a set with an even number of vertices of T. Design a polynomial time algorithm that finds |S|/2 simple and disjoint paths in edges matching pairs of vertices in S. ...
1
vote
0answers
23 views
Solving a pursuit-evasion game
Let's say we have a simple connected and undirected graph $G(V,E)$. The game is played with two players. For each game, player A starts at a node $t$, and player B at a node $v$. There is also a node $...
1
vote
1answer
22 views
Word ladder problem for words with different length
Is there some one who know any algorithm for word ladder problem with words of different length?
Actually we have some strings with same length and some strings with one length longer but not from ...
1
vote
1answer
43 views
Proving correctness of inefficient algorithm - Path between two vertices
Consider the following inefficient algorithm that decides if there is a path between two vertices s and t of a directed graph G. Show that the algorithm is correct. In addition, analyze its complexity ...
0
votes
0answers
18 views
Counting chords intersections in a circle
The problem is:
Given 2n distinct endpoints of n chords on the unit circle, count the number of intersections between chords (if k chords intersect at one point,
that point counts as $\binom{n}{2}$ ...
0
votes
2answers
31 views
“Process functions” in iterative and recursive depth-first search
I was reading The Algorithm Design Manual by Steven Skiena, and I noticed his use of "process functions" in depth-first search and breadth-first search. Consider the following pseudocode for depth-...
0
votes
0answers
10 views
Lazily Distributing Elements on a Fixed 2D Matrix
I'm trying to create a small game as part of a programming exercise, and was trying to devise a way to lazily create a 2D map for the player while they traverse it, finding resources.
Players are ...
0
votes
0answers
27 views
Practical computation time, counting spanning trees and selecting spanning trees uniformly at random
I am doing a project in applied math, which involves counting spanning trees and selecting spanning trees uniformly at random for near-maximal planar graphs with ~430 vertices, as part of a larger ...
4
votes
3answers
235 views
Hard connected instances for Weisfeiler-Lehman test of isomorphism
There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm.
However, one of these graphs is disconnected. So what are the instances ...
1
vote
0answers
14 views
Relation between deficiency and color class parity of graphs
Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
0
votes
0answers
7 views
What is the expected number of matching pairs in a stable matching problem
What is the expected number of matching pairs in a stable matching problem involving n companies and n applicants where each company and applicant has their own independently generated preference list?...
2
votes
1answer
21 views
Given a set of intervals on the real line, find a minimum set of points that “cover” all the intervals
I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval ...
2
votes
0answers
30 views
Method to calculate score in a go game
I'm currently programming a go game, and I'm struggling with some aspect of the game, especially how to handle the end game, how to count points and how to detect dead stones ?
I thought of doing a ...
1
vote
2answers
39 views
Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights
Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for ...
0
votes
1answer
33 views
Graph Edit Distance
Source: K. Riesen, Structural Pattern Recognition with Graph Edit Distance,
Advances in Computer Vision and Pattern Recognition.
Link: https://www.springer.com/cda/content/document/...
0
votes
0answers
9 views
How can we implement efficiently a maximum set coverage arc of fixed cardinality?
I am working on solving the following problem and implement the solution in C++.
Let us assume that we have an oriented weighted graph $G = (V, A, w)$ and $P$ a set of persons.
We receive a number ...
