Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

219 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
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 ...
1
vote
0answers
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$, ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 /...
1
vote
0answers
126 views

About the sparsest-cut question

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, ...
1
vote
0answers
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 ...
1
vote
0answers
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 ?
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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) ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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?
1
vote
0answers
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'}$ ...
1
vote
0answers
312 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
1
vote
0answers
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: ...
1
vote
1answer
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.
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
222 views

What's the fastest algorithm to compute Max{max flow with single source and multiple sinks}

Given an arbitrary directed graph(not planar, cycles included), a source node $S$ and constant constraints on edges, for each sink node $t_i$, the maximum flow from $S$ to $t_i$ is denoted by $f(S,t_i)...
0
votes
0answers
976 views

How to solve such a graph optimization problem?

I have a graph optimization problem which is hard to describe in the title. There is a component based system which consists of components and data transmissions between components(components and ...
0
votes
0answers
130 views

CSP-problem, based on context-free grammar

I'm trying to solve a CSP (Constraint-Satisfaction-Problem), which is based on arbitrary context-free grammars. A quick example: Let's say we have a context-free grammar with the following production ...
0
votes
0answers
76 views

Detect highly weighted but also densely inter-connected subnetworks

In a connected / undirected / node weighted (with both positive and negative weights) network, there are many papers studied about the 'Maximum weight connected subgraph' problem. But are there any ...
0
votes
0answers
153 views

Transitive reduction not provably minimal

Working on finding minimal equivalent graphs, which unlike transitive reductions only allows for edge removals from the original graph. I was under the impression that if you allow for new edges to be ...
0
votes
0answers
73 views

DAG reduce edges by transitivity

I have a DAG like this $G_1 = \lbrace A \to B \to C \rbrace$ My algorithm modify $G_1$ so it will be like this $ G_2 = \lbrace A \to C, B \to C \rbrace $ I now that $G_2$ is not a transitive ...
0
votes
0answers
186 views

Efficiently computing propagation values for only a few positions in a grid

Consider a matrix filled with some nodes containing positive integers ("starts"), some nodes marked as a wall, and the rest of the nodes given a value of infinity. The propogation rule is simple: For ...
0
votes
0answers
134 views

Distance oracles in trees

Given an unweighted tree $T=(V,E)$ what is the minimum number of distance oracles that allow to detect the position in the graph of every node $v$? A distance oracle is "special node" $u$ of the ...
0
votes
0answers
402 views

Rectangular constraints in Delaunay Triangulation without edges within

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