# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

219 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k views

### Fastest Algorithm for the Minimum Edge Covering Problem

Given an undirected weighted graph, G, where all the weights are non-zero positive numbers, my algorithm must produce a sub-graph G' that satisfies the following constraints: G' must include all the ...
97 views

### Detecting bridges in Hypergraph S-t Reachability

Is there a fast algorithm to detect possible bridge arcs in hyperpaths from set $S$ of nodes to node $t$ in a hypergraph $G$. That is, given a hypergraph $G$, source nodes $S$, and target node $t$, ...
94 views

### Concentration Bounds for functions of matrices

This is a question about properties of large directed graphs which are preserved when we randomly sample edges. Imagine I have an infinite sequence of positively weighted directed graphs. The ...
104 views

### algorithms for a large submatrix / general factor / quasi-biclique problem?

Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that ...
142 views

### Vertices adjacent to Exterior region of a Planar Graph(Algorithm)

Problem: I am looking for an algorithm which finds all vertices that are adjacent to exterior region of a planar graph(For a planar graph, any region=face can be considered as the exterior region /...
126 views

Can someone kindly help clarify as to exactly what is the generally accepted definition of the "sparsest cut" problem for a graph? (Isn't the set which achieves the Cheeger constant for a graph, ...
108 views

### Pruning a graph by removing vertices not part of any minimal Steiner tree

Given a sizable graph $G = (V, E)$, with $|V| \approx 1400$ vertices and $|E| \approx 1600$ edges, I have an optimization problem to find a connected subgraph of $G$ of size $k$ such that a given ...
173 views

### Minimum Clique edge cover to cilque vertex cover

Suppose, there is an algorithm for enumerating minimum clique edge cover. Is it always possible to convert the algorithm to enumerate clique vertex cover ?
189 views

### Help with a special case for Hungarian algorithm

I am working on a problem and it appears to be a special case of Hungarian algorithm. In Hungarian algorithm for assignment problem, there are n people and n jobs. Each person can do any of n jobs ...
133 views

### Predicting the growth of a social network

I am building a predictive model for the growth of the amount of users of a new p2p protocol inspired by bitcoin and I would like to use historical data collected from the growth of major social ...
58 views

### Repartitioning a binary tree

Suppose I have a binary tree $G = (V, E)$ (with undirected edges) that is partitioned into sets of k vertices, where each set of vertices is a connected subgraph of $G$. Additionally, if there are ...
60 views

### Partition planar graph of vertices with at most degree 3 into connected subgraphs

I'm currently working on my thesis which deals with pathfinding over a Delaunay triangulated graph. I want to be able to partition my Delaunay triangulation into disjoint (regarding vertices) ...
52 views

### Finding if an edge lies within a set of disjoint rectangles

I'm using a triangulation library to compute the Constrained Delaunay Triangulation of a set of rectangles within some large boundary. The algorithm returns all the edges, but also adds edges inside ...
468 views

### Time complexity of clustering based on random walk

What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph? Can I use the complexity of eigen vector computation for this purpose? The ...
93 views

### Decidability one relation, binary FOL over finite models

Suppose $\sigma$ is a vocabulary consisting of one binary relation $E$ and let $\phi$ be a $\sigma$ sentence. Is it decidable whether there is a finite directed graph $G$, with all in- and out-degrees ...
853 views

### Finding minimum weight $k$ cliques in a complete graph

For an undirected weighted complete graph $G = (V, E)$. Assuming the edge weight indicates the similarity between different nodes, the smaller $w_{ij}$ is, it means $i$ and $j$ are more similar ...
996 views

### Using Max-Flow (Ford Fulkerson) to find satisfying flow

i am trying to find a first allowed flow from vertex q to vertex s in a network N which has both minimum and maximum capacities. 1.) To solve the problem I started by creating a helper network NH by ...
2k views

### Finding two vertices with the most/least common neighbors

I am not a computer scientist so please bear with me if this is a naive question. Take any graph, pick a set S of vertices (by some criteria or random). Find two vertices in set S with the most/least ...
1k views

### Widest path between s and t with additional constraints

Given a directed graph G and vertices s and t, the maximum capacity path between s and t is the path for which the minimum edge on the path is maximum, among all such s-t paths. Now I can use a ...
191 views

### Map points from one plane into another

Given a point on a plane A, I want to be able to map to a corresponding point on plane B. I have a set of N corresponding pairs of reference points between the two planes, however, the overall mapping ...
141 views

### Connection strength in a weighted social digraph, based on weights of individual links

Given a network where edges represent entities and directed vertices represent relationships between entities, and each vertex has a strength between 0 (no relationship) and 1 (strongest). I'm ...
118 views

### Min-cut variation

I'm searching for an algorithm to do the following I have a graph $G = (V, E)$ and a set of terminal pairs $\{(s_i, t_i)\}$. I need to find a cut smaller than a given quantity $k$, such that there is ...
151 views

### Is there an algorithm for finding the maximal edge weight over all spanning trees?

Let $G = (V,E)$ with a weight function $w(e)$ for $e \in E$. Let $T$ be the set of minimal spanning trees of $G$. I am interested in finding $\min_{t \in T} \max_{e \in t} w(e)$, where $t$ ranges ...
93 views

### Belief Propagation on MRF with complex cliques

Is there a belief propagation algorithm for exact inference on a MRF with complex clique structures (i.e. ones involving more than 2 neighbours)? For MRF's with cliques that only involve pairwise ...
68 views

### Strategies for preventing isolated nodes in a dynamically changing undirected cyclic graph

I'm building a mesh network where i need to detect the unexpected disappearance of a peer. Each node attempts to stay in communication with at least X peers. A node refuses connection from another ...
135 views

### Optimal inlining algorithm

I seek an algorithm to optimise the process of inlinling. Is there such an algorithm, or set of such algorithms? Is there an efficient functional algorithm? To be specific assume we have an Algol ...
196 views

### Algorithm for permuting elements using constant work space

I'm searching for an algorithm to do the following: A 1->3 B 2->6 C 4->5 D 5->2 E 6->4 F 3->7 G 8->9 H 10->11 Elements A-H are stored on ...
89 views

### Resources to get started on fractional graph coloring algorithms

I'm interested in using fractional graph coloring algorithms/solvers to solve a problem, where is a good place to start? I'm looking to find basic/introductory to state-of-the-art algorithms more ...
357 views

### Discovering a graph with minimal oracle queries

I have a transitive DAG G which is a subgraph of an unknown DAG R. (The nodes are the same in G and R, but R may have edges not in G.) I can determine the presence of a given edge in R by an oracle ...
246 views

### How to quantify the tree-like-ness of a graph?

What are good measures of tree-like-ness of a graph and algorithms for calculating them?
537 views

### Minimum Weight Disconnected Subgraph and “Opposite” problems

Given a graph $G = (V,E)$ and a vertex weight $z_v$ for each $v \in V$, find an (EDIT) induced subgraph $G' = (V', E')$ with minimum weight $z_{G'}=\sum_{v' \in V'} z_{v'}$ ...
312 views

### Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g.  Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
2k views

### DAG partitioning to subgraphs

Given a DAG with $|V| = n$ and has $s$ sources, we have to present subgraphs such that each subgraph has approximately $k_1=\sqrt{s}$ sources and approximately $k_2=\sqrt{n}$ nodes. (Note: ...
1k views

### Finding the nearest node to a given set of nodes in a graph

I am looking for an algorithm that, given a large weighted undirected graph, would find the node that has minimum average distance from a given set of nodes in the graph.
9 views

### Existence of graphs of every order related to Barnette’s conjecture

Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous Barnette’s conjecture is based. My interest in C3CBP graphs is somewhat orthogonal ...
44 views

### Matching of two weighted graphs allowing one-to-many mapping

I am looking for a heuristic for a graph matching problem as follows. Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
20 views

### Connectivity with ordered adjacency list

In the adjacency list model, a graph is described through lists that contain the neighbors of any node $i \in [n]$. A query is of the form "What is the $k$-th neighbor of node $i$?". BFS allows to ...
68 views

### Unknown gaps in computation models

I'm looking for computatuon models where it is known that there are problems that we can solve in time T1 and T2. where T1 is smaller then T2 and it is unknown if there are problems where their ...
19 views

### The set of weight functions for which the assignment problem has non-trivial solutions

The standard assignment problem is specified with a square matrix ${\bf W}$ of weights (values, costs): $$V_{\cal P} = \sum_i w(i, b(i)) = \sum_{(i, j) \in {\cal P}} w_{ij},$$ where $\cal P$ is a ...
30 views

### Alternating Delivery Problem

What is known about the complexity of the following problem: Suppose we have a complete bipartite graph $G(V,E)$ with disjoint sets $C$ and $T$. The candidate vertices, and the target vertices ...
60 views

### About complexity of recovering or learning Bayesian networks

Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having ...