The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

845 questions
Filter by
Sorted by
Tagged with
256 views

Optimization Problem on a Directed Graph

I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For ...
9k views

Vertex Cover applications in the real world

What applications does the Vertex Cover Problem have in the real world? Which industry or research projects use actually implemented software that is based on theoretical results for the Vertex Cover ...
46 views

Randomized algorithm for clique that proves P = NP [closed]

Suppose there is a polynomial-time randomized algorithm which for graph $G$ and natural number $k$ with probability not less than $2/3$ correctly answers the question whether or not there is a clique ...
73 views

Finding simple fixed length paths in directed graphs

Is there an efficient algorithm to enumerate unique simple fixed-length paths (of size $k$) in directed graphs? What would be its time complexity?
66 views

121 views

Shortest s-t path when is allowed to ignore k weights

Given an undirected graph $G$ with $n$ vertices and $m$ edges, with non-negative weights on the edges, what's the best algorithm that computes the shortest path from $s$ to $t$, where you are allowed ...
606 views

Computing a transitive completion / path existence oracle

There has been a few questions (1, 2, 3) about transitive completion here that made me think if something like this is possible: Assume we get an input directed graph $G$ and would like to answer ...
63 views

Complexity status of the Edge Deletion problem to bounded degree graphs

I'm interested in the complexity status of the following problem. Input: a graph $G=(V,E)$ and two natural numbers $k$ and $d$. Output: Yes, if there exists a subset $E' \subseteq E$ of cardinality ...
145 views

How is SDP an extension of spectral algorithms?

In one of his lectures, Uri Feige described semidefinite programming (SDP) as ... an algorithmic technique that extends both linear programming and spectral algorithms. I know the basic ...
3k views

What are the algorithms and the data structures for GUIs and input management?

I'm studying how, given: an input from the user ( like a click of the mouse or the input from a key ) a well defined data structure that represent the graphical layout inside a window ( a tree/graph ...
143 views

Data Strcuture to represent dependencies amongst modules

Consider several software modules $m_1, m_2, ... m_n$. Each module has some inputs and outputs and the inputs to some of the modules are dependent on the outputs of some other modes. For example, in ...
667 views

Graph classes for which the diameter can be computed in linear time

Recall the diameter of a graph $G$ is the length of a longest shortest path in $G$. Given a graph, an obvious algorithm for computing $\text{diam}(G)$ solves the all-pairs shortest path problem (APSP) ...
A (n, m, k)-bipartite graph is a bipartite graphs with: independent sets of size $\{n, m\}$ a total of $k \geq n+m-1$ edges We want an algorithm to generate a (n, m, k)-bipartite selected uniformly ...