Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

Filter by
Sorted by
Tagged with
0
votes
1answer
161 views

Literature request: Generating all vertex subsets of a graph

I am working in an algorithm which finds a unique maximal independent set of vertices. Then, using this set, one can construct all other vertex subsets. I assume this might have some applications ...
0
votes
0answers
14 views

Is there an algorithm to efficiently generate all partitions of a set such that no cell contains fewer than k elements of the set?

I am trying to generate partitions of networks to evaluate clustering algorithms. I know that generating all partitions is infeasible (since they grow with Stirling number of the second kind which get ...
0
votes
0answers
18 views

Show the relations between numerations in a graph

I currently have a bit of a problem with one at least simple looking assignment. I am given a graph, which i will post as a image for reference. I had to number it after pre-ordering $r[]$, post-...
5
votes
0answers
81 views
+50

Optimization on hypergraph "refinements"

Given a hypergraph $H = (V, E)$, call $H' = (V, E')$ a refinement of $H$ iff there exists a partition $p : E' \to I$ (where $I$ is an arbitrary index set) such that $E = \{\bigcup_{x \in p^{-1}(i)} x \...
0
votes
1answer
14 views

Calculate post dominator with non exiting control flow

Using the basic algorithm to calculate post dominators I run into trouble when working with a CFG containing an infinite loop (i.e., not terminating). The algorithm: ...
0
votes
1answer
33 views

Prove there is an algorithm that needs at most n-1 comparisons to check if n-element array has all equal elements?

Question: Prove that there exists an algorithm that can decide using at most n-1 comparisons whether a n-element array contains only equal numbers. We use an algorithm that loops through all the ...
0
votes
1answer
68 views

How to find the maximum number of square groups in a board

I'm stuck with the following problem: Given an n*m board, find the maximum number of square groups that can be positioned on the board. What are square groups? They contain 4 distinct squares named: ...
1
vote
0answers
14 views

Finding highly-connected regions of graphs

I have a large network of 10,000 nodes and I am trying to identify subgraphs which are clique-like, in that they share many connections. I don't a priori know how many subgraphs fit this criteria. To ...
0
votes
1answer
12 views

Define a directed edge in a DAG using partial ordering

I am trying to describe a novel type of DAG's construction algorithm. The directed edges of the graph corresponds to a partial ordering: i.e. any directed edge $e$ spanning from $f$ to $t$ also ...
0
votes
0answers
17 views

Polynomial Deterministic Algorithm for MAX-QP problem with multiplicative errror $1/n$

MAX-QP problem (quadratic programming on boolean cube) statement: Given symmetrical matrix $A$ with 0 on diagonal $$A = (a_{ij}) : A^T = A, a_{ii} = 0$$ Find maximum $x^TAx$ where $x \in \{0, 1\}^n$, ...
1
vote
1answer
7 views

Max-Min Weighted Matching

The maximum weighted matching problem (https://en.wikipedia.org/wiki/Maximum_weight_matching) finds a matching in a weighted graph that has maximum sum of weights. I was wondering if there are any ...
1
vote
0answers
14 views

A paper seems to mention a planar graph's "faces" in an embedding-less context

I am trying to implement the "DWR algorithm" described in Fig. 2 of This Paper (in order to get a program that reduces a planar graph to K2 using solely loop removal, leaf removal, "...
3
votes
1answer
99 views

Winning move in graph based strategy game

I'm prototyping a deterministic Risk like game. A player can move units from one node to a connected node if he has more than 1 unit the in origin node (must leave 1 unit behind). The player wins if ...
0
votes
0answers
7 views

Count all independent sets and cliques of an undirected graph

I need to write a Java program that tells if a graph is a (k, l)-graph or not, that is, if we can partition its set of vertices into k independent sets and l cliques. Then I would need to build a ...
1
vote
1answer
103 views

Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree

CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have ...
7
votes
0answers
85 views

Optimality of DSATUR on interval graphs

The DSATUR algorithm is a greedy graph coloring algorithm. It consists of applying the usual greedy coloring algorithm, considering vertices in reverse lexicographic order of (number of different ...
2
votes
1answer
74 views

D* Lite - can edge costs be asymmetric?

I'm trying to modify the original D* Lite algorithm adding a margin constraint wrt to any nearby obstacle to be satisfied for each selected cell in the path. This causes the edge cost function between ...
2
votes
1answer
3k views

Prove that a hamiltonian DAG has a single topological sort

I've been straggling a little proving the argument "a hamiltonian directed acyclic graph has a single topological sort". This is pretty much the idea of what I've come along: lets prove by ...
0
votes
1answer
29 views

strange and different conclusions about Bellman Ford

Recently I asked a question Here about following topics: after finishing bellman ford algorithm, if BF continue to update distances and distance value related to one vertex v being updated,then v is ...
1
vote
1answer
20 views

Finding a minimum spanning tree that shares the minimum number of edges with the given one

Given some undirected weighted graph $\ G(V,E, w) $ and its minimum spanning tree $\ T$, I need to find another spanning tree $\ T' $ with minimal amount of common edges of both trees. If there are no ...
0
votes
0answers
16 views

graph representation of a Boolean function

I'm trying to classify a certain family of Boolean functions, and need to represent the function as a graph. Is there any well-known graph representation for a Boolean function that captures the ...
0
votes
1answer
447 views

What time complexity is a reachability algorithm?

I've read there are ways you can determine all reachable pairs using Strongly Connected Components. But, I want to calculate all reachable nodes on the fly - so I don't have to store a massive ...
4
votes
1answer
873 views

Showing Cycle is NL-complete?

Consider the following decision problem : Cycle: Given a directed graph G, does G contains a directed cycle? It is very clear why Cycle belongs to NL. My question is - how to show Cycle is ...
1
vote
1answer
55 views

Prove the following claim on Hamilton Path?

I am trying to prove the following claim: Given DAG graph, there is Hamilton path iff the following algorithm returns true: Do topologic sorting. Move on the graph's vertices one by one (from low to ...
5
votes
3answers
6k views

What's the Big O runtime of a DFS word search through a matrix?

The problem is to try and find a word in a 2D matrix of characters: Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent ...
0
votes
0answers
9 views

A DFS update without re-running DFS after adding and removing an edge

Given an undirected graph $G=(V,E)$ I perform a DFS run on it, and among other information I get the visit time $s(\cdot )$ and the exit time $f(\cdot )$ per each node and the parent of each node. ...
1
vote
0answers
35 views

Graph in which greedy algorithm for maximum matching is a 2-approximation

Here is a greedy algorithm for maximum bipartite matching: Iteratively select an edge that is not incident to previously selected edges. This algorithm returns a 2-approximation, and runs in linear ...
2
votes
1answer
52 views

Maximum independent subset for graphs with lots of edges

Consider an NP-hard graph problem, like the maximum independent set problem. Let us say I restrict my inputs to only be graphs that have $n$ vertices and at least $n^{c}$ edges, for some $c > 1$. ...
4
votes
1answer
39 views

How can we process these types of queries on trees?

CAN SOMEONE FIND A BETTER (MORE DESCRIPTIVE) NAME FOR THIS QUESTION, THANKS I recently thought of this interesting Tree problem: Given a tree with $N$ nodes, let $val_i$ = the "value" for ...
2
votes
1answer
91 views

Max flow algorithm for floating-point weights and E~=10*V

Could you, please, suggest a maximum flow algorithm for a graph with floating-point weights and the number of edges approximately equal to the number of vertices? I.e. ...
2
votes
1answer
36 views

Minimum number of edges to remove from a graph, so that MST contains a certain edge

Let's suppose we have a weighted and connected graph. We can easily find the minimum spanning tree for this graph. But let's say we want to "force" a certain edge $e$ to be in the MST. For ...
1
vote
1answer
18 views

Reducing a seating problem to maximum flow

Problem: We have p different families with $1 \leq i \leq p$ members for the $i$-th family. We also have q tables where table $t_j$ has a capacity of $1 \leq j \leq q$. We want no two members of a ...
0
votes
0answers
12 views

Detect the actual edges of circle in directed graph [duplicate]

Okay so , I know how bellman -ford can detect a negative circle. My question is : how to actually find the edges participating in this circle. I searched and found some stuff that seem to work in the ...
1
vote
1answer
1k views

Updating a mst after increasing the weight of an edge in the mst

Suppose we have a weighted undirected graph $G$ and a minimum spanning tree $T$ Let $G2$ be a new graph by increasing the weight of one edge $e = (a,b)$ that is part of $T$. I'm using a common ...
1
vote
0answers
15 views

How to find if there's an MST where vertex $v$ has degree 2 in it? [duplicate]

I've faced this question and I hope that someone can help with it. Question: We're given an undirected graph $G=(V,E,w)$ where $w\colon E\rightarrow \mathbb{Q}$ and vertex $v$. We want to find if ...
1
vote
1answer
74 views

How to get the shortest simple path in a directed Graph with an additional constraint that it needs to use two arcs in the said path

I have a directed graph that has positive weights (but there are reverse arcs) and I am trying to find the shortest path between a given source, s and a given sink, ...
0
votes
2answers
660 views

CLRS Exercise 24.3-4 - Confirm Output of a Program Claiming to Implement Dijkstra's Algorithm

I'm trying to better understand Question 24.3-4 From CLRS below: Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for ...
1
vote
1answer
64 views

Exit quickly from a maze with a local view of the maze

How to efficiently exit from a maze where you know the initial position of the player (1,1), the exit (49,49)? You don't know the maze configuration but you know where your player is, and which ...
-1
votes
0answers
52 views

Maximum flow: Dining problem

I have a network flow problem: There are $n$ people invited to a party, the age of person $i$ is $a_i$ years, the waiter must position them in a way such that: Everyone sits around a table There are ...
1
vote
0answers
25 views

Graph based on strings of turing machine

For a $\Sigma$ with characters $0,1,$#$,\sigma_1,...,\sigma_m$. I have any $M$ that is a deterministic turing machine. Fix a $n$ (natural). i look at the following graph constructed from the turing ...
0
votes
2answers
165 views

Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k

I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G. My algorithm is as follows: Generate all subgraphs of size k, and check ...
11
votes
1answer
11k views

How to reduce the number of crossing edges in a diagram?

I am working on a diagram editor. Diagrams display 2D shapes (nodes) connected with connectors (edges). I'd like to add an operation that, given a selection of nodes, "disentangles" them: it ...
3
votes
2answers
118 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 ...
0
votes
1answer
120 views

Kernelization algorithm for the following problem

We are given an undirected graph $ G $ and a positive parameter $ k \geq 0 $. The problem is to decide if there exists a set $ S \subseteq V(G) $ of size at most $ k $ such that $ G − S $ does not ...
0
votes
2answers
307 views

Write a pseudo code for a Graph algorithm

Given a DAG $G=(V, E)$ and a function $f(v)$ which maps every vertex to a unique number from 1 to $|V|$, I need to write a pseudo code for an algorithm that finds for every $v\in V$ the minimal value ...
0
votes
1answer
82 views

Algorithm for display nodes of a particular node based on in-degree and out-degree

Suppose we have following directed graph. When I click on say node $e$, it should make in-degree and out-degree of node $e$ and connected nodes red. As shown in Resulting Graph. My purpose is, when I ...
7
votes
1answer
642 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
1
vote
1answer
141 views

communities problem with union and find

I am trying to solve the following problem: Input is $2D$ array of integers, $M$, which corresponds to friendship relations. For example, if $M[1][2]=1$, $1$ and $2$ are friends (assuming symmetry it ...
1
vote
1answer
34 views

Fastest way to find optimal graph coloring in polynomial space given chromatic number

Suppose I have a graph's chromatic number. Give a faster-than-brute-force polynomial-space algorithm for finding an optimal coloring. If such an algorithm isn't known, please tell me so. This question ...
0
votes
1answer
19 views

About a possible optimized version of Johnson's algorithm on a DAG with "elementary circuits"

Recently I came upon the Johnson's algorithm to find "elementary circuits" on a directed graph, which is really cool to me. I'm just implementing it from scratch in C++ following the ...

1
2 3 4 5
87