Algorithms on graphs, excluding heuristics.
0
votes
0answers
28 views
deduction on a network flow when the flow value given in advance using ford fulkerson algorithm [migrated]
I need your help with an exercise on ford fulkerson.
Suppose you are given a flow network with capacities (G,s,t) and you are also given the max flow in advance (|f|).
Now suppose you are given an ...
3
votes
1answer
74 views
Partition graph into complete disjoint subgraphs while maximising sum of edge weights
Has this problem been studied?
We start with a complete, simple, undirected graph with edge weights. The problem is to delete edges so as to partition the graph into complete disjoint subgraphs while ...
-3
votes
0answers
26 views
Worst case scenario in binary tree search [migrated]
I am a freshman in Computer Science University, so please give me a understandable justification.
Well, i have a binary tree that is equilibrated by height witch has 635 nodes, what is the number of ...
-1
votes
0answers
25 views
A* for utility maximization in path finding [closed]
The A* algorithm is usually implemented in such cases in which the shortest path from a node to another in a graph G has to be found. At each step, the node minimizing
f(n) = g(n) + h(n)
is selected ...
4
votes
1answer
106 views
Perfectly matchable edges in a bipartite graph
Consider the following problem:
Given a bipartite graph $G = (V, E)$, an unmatched edge is one that does not appear in any perfect matching. Design an algorithm to find all unmatched edges. (assume ...
4
votes
0answers
103 views
Biconnected components of a directed graph?
I am looking for an algorithm for computing the biconnected components of a strongly connected directed graph.
5
votes
4answers
156 views
An algorithm for calculating the probability of a disease spreading through a graph
The following problem came up in my undergrad research project: You have some undirected graph. Some nodes are "sick" and some are not. The probability that a neighbour of a sick node becomes sick is ...
0
votes
1answer
92 views
Expansion vs Sparsest cut
let $G=(V,E)$ and $S\subsetneq V$ then expansion of set $S$ is
$$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}}$$
where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges ...
4
votes
0answers
85 views
Long Cycle in Bounded Tree-Width Graphs using DFS and Dynamic Programming
For fixed parameter $k$, I would like to find a long cycle of length $\geq k$ in an undirected graph $G(V,E)$. This can be done in $O(k!2^k|V|)$-time [2] using 1) depth-first search (DFS) and 2) ...
4
votes
0answers
83 views
Weighted vertex-connectivity; global min vertex-cut
I am interested in the following problem:
Input: a connected undirected graph $G=(V,E)$; a positive weight for each vertex.
Output: a minimum weight subset of $V$ whose removal disconnects ...
-1
votes
0answers
75 views
Study groups for theoretical computer science aspirants [migrated]
Recently I decided to go deeper on the subjects like automata, algorithms and graph theory etc. but while reading these either I feel bored or confused hence instead of passive learning I want ...
-1
votes
0answers
121 views
Linear algorithm to find if graph is friendly [closed]
We have a directed graph G=(V,E). Graph called friendly if for every two verticals
u and v there is a path from u to v or form v to u.
Is it possible to find if G is friendly in linear time? I ...
-3
votes
0answers
68 views
Algorithm in NP for the k-coloring problem [closed]
Does a generic algorithm exist that I could implement in an application to solve the $k$-coloring problem for any $k$ colors? I understand that such an algorithm would be $NP$, I'm just having trouble ...
0
votes
0answers
39 views
Sparse inverse covariance estimation in high dimensional data
I am trying to estimate the sparse inverse covariance matrix in very high dimensional data, I mean with million variables. Up to now all the papers like this that I have found, they are limited to ...
4
votes
2answers
202 views
Approximation algorithm for finding the maximum common subgraph in two DAGs
Suppose we have two directed acyclic graphs $A$ and $B$ and we look to find the subgraph that is common to both graphs and has the most number of vertices. That is to find the biggest graph which is a ...
-1
votes
1answer
54 views
Consensus impossibility for arbitrary graph $G$
I know the proof of impossibility of achieving deterministic algorithm for consensus (the basic synchronous model) for 2 processes.
What is the proof for an arbitrary graph?
6
votes
1answer
132 views
Shortest paths perturbation
I have a graph $G=(V,E)$, with positive weights $w_e, e\in E$ on the edges, and I would like to randomly perturb the weights of the edges so that for each pair of distinct vertices $(u,v)$ such that ...
3
votes
0answers
97 views
Min Weight Complete bipartite subgraph
Suppose we are given a large bipartite graph with weighted edges, and a small parameter $d$ (e.g. $d$ is 3 or 4).
What is known about the run-time to find the minimum weight complete bipartite ...
0
votes
1answer
97 views
directed or bidirected in relation to mssp (Multiple source shortest path)
Firstly I wanted to ask. If I have a undirected graph and split all the edges into two directed edges is it still called directed or does it become bi-directed?
this is a picture of what I mean
The ...
4
votes
0answers
258 views
Multiple-sources dominator trees: compact representation and fast algorithm?
I recently learnt about the concept of dominator trees and was fascinated by it.
I was wondering how the problem extends to computing dominators from multiple sources, or even from all vertices in ...
0
votes
1answer
55 views
Designing a Transport network path suggestion tool
I am working on a suggestion system to passengers on transits to take.
The thing is we are formulating stations on a transport network (eg. bus transport) as nodes and route between spatially adjacent ...
2
votes
1answer
159 views
Finding the shortest path in the presence of negative cycles
Given a directed cyclic graph where the weight of each edge may be negative the concept of a "shortest path" only makes sense if there are no negative cycles, and in that case you can apply the ...
8
votes
1answer
1k views
Complexity of computing the average distance of a graph
Let $\rm{ad}(G)$ be the average distance of a connected graph $G.$
One way to compute $\rm{ad}(G)$ is by summing up the elements of $D(G),$ the distance matrix of $G$ and scaling the sum ...
1
vote
0answers
32 views
Length functions in blocking flows
I've been attempting to read Goldberg & Rao's paper Beyond the flow decomposition barrier, and found that I could not understand the blocking flow component of the paper. I then found Karger's ...
16
votes
1answer
428 views
Count the number of spanning trees fast
Let $t(G)$ denote the number of spanning trees in a graph $G$ with $n$ vertices. There is an algorithm that computes $t(G)$ in $O(n^3)$ arithmetic operations. This algorithm is to compute ...
8
votes
0answers
134 views
How fast can we compute the set inclusion poset of a set family?
Given a set family $\mathcal{F}$ of subsets of a universe $U$.
Let $S_1,S_2 \in \mathcal F$ and we want to answer is $S_1 \subseteq S_2$.
I am looking for a data-structure that will allow me to ...
0
votes
0answers
122 views
Generate TSP instances with known optimal
Is there a known (polynomial in number of nodes) algorithm to generate TSP instances with known optimal value?
The idea is to be able to generating arbitrary large instances with known optimal ...
4
votes
0answers
103 views
Fast algorithm for successively merging k-overlapping sets?
Consider the following algorithm for clustering sets: Begin with $n$ sets, $S_1, S_2, \ldots,S_n$, such that $$\sum_{i = 1}^n |S_i| = m \,,$$ and successively merge sets with at least $k$ elements in ...
2
votes
2answers
220 views
Fastest way to find an s-t min-cut from an s-t max-flow?
Ford-Fulkerson can find sparse s-t flows in time linear in the size of the flow and number of nodes if the edges have unit capacity.
How could I use a sparse s-t flow to find an s-t min-cut in time ...
1
vote
0answers
43 views
Help with the definition of clique percolation
So I can find the Wiki article okay, as I think I understand that this is a definition of a special community in a graph. However their image in Fig. 1 confuses me from the description.
As I ...
11
votes
2answers
823 views
Small graph with gap between chromatic and vector chromatic number?
I’m looking for a small graph $G$ whose vector chromatic number is smaller than the chromatic number, $\chi_v(G)<\chi(G)$.
($G$ has vector chromatic number $q$ if there is an assignment $x\colon V ...
2
votes
1answer
86 views
Verifying consistency of strict and non-strict partial orders constraints
I am building a set of constraints of the kind $x < y$ and $x \leq y$, where $<$ is a strict order and $\leq$ is a non-strict order on the same set, and $x$ and $y$ are abstract variables ...
0
votes
0answers
46 views
DFS and c-Expander graph - simple path with the length of n-2c+1 [closed]
Just to make it clear - c-Expander graph is a directed graph G(V,E) with 2 Disjoint sets (A and B), of size equal or more than c with at least one Vertex between node of A and node of B.
I have to ...
3
votes
2answers
147 views
Follow-the-leader algorithm in swarm formation: literature on the subject?
In an AI strategy game simulation, I devised an algorithm for forming a group and swarming a known location without communication among soldiers (ie. every individual agent makes a locally optimum ...
0
votes
0answers
56 views
Nonnegative Permanent and Ellipsoidal Method
Famously, Barahona gave an algorithm for Max Cut for Graphs without K5 complete as Subfactor Graph.
This was based on the Ellipsoidal Method.
Finding a Max Cut is the same for Bipartite Graphs as ...
0
votes
1answer
215 views
Approximation algorithm for graph problem
In the process of trying to create an approximation algorithm for the following problem.
Let $G = (V,E)$ be a graph, $c_e, c_{iv} \ge 0$, for $e \in E$, $i \in L$, and $v \in V$, where $L$ is a ...
3
votes
1answer
158 views
Breadth first search and Eppstein K shortest paths algorithm
I'm trying to understand the algorithm for finding K shortest paths in a graph described by Eppstein in this paper: http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf
I have trouble particularly ...
7
votes
1answer
137 views
Approximation algorithms for Directed Minimum Cut with Cardinality Constraints
We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature.
...
6
votes
1answer
151 views
Finding appropriate spanning tree of connected bipartite graph
I got this as a sub-problem while working on a research problem connected to index coding. Can someone please give me directions as to how to approach this problem?
Problem: We have a connected ...
1
vote
0answers
63 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 ...
6
votes
2answers
199 views
Caterpillar decomposition of trees
Can any tree on $n$ nodes be decomposed into a set of $O(\log n)$ caterpillars? If not, what is the maximum number of caterpillars required? Are there efficient algorithms for finding the ...
0
votes
0answers
120 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 ...
0
votes
1answer
61 views
Source sending 0 transport units
I have a network flow (with min and max capacities) where the only transport units flowing are within a cycle (of flow value 2). The source of the network does not send out any transport units into ...
7
votes
1answer
281 views
Goldberg&Tarjan: How to find a blocking flow in a graph
I want to implement the Goldberg & Rao algorithm for finding a maxflow in a graph. My problem is the update step where every paper and report is stating "In the resulting graph, find a blocking ...
1
vote
0answers
249 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 ...
0
votes
2answers
190 views
Constrained shortest path problem
Here is my problem:
I have an undirected graph (with loops). We have k different classes of vertices in the graph. You can think of class 1 vertex being colored green, class 2 vertices colored red and ...
0
votes
2answers
160 views
Find minimum number of transformations to transform from input to target string
Given that I have an input string, for example: aab
And I am given a target string, for example: bababa
And then I am given a ...
-4
votes
1answer
264 views
Algorithm to find shortest path from a set of nodes to another set of nodes? [closed]
I'm developing a route planner, and I was reading some graph theory.
I read a little bit of Dijkstra's shortest path, shooting star and turn restrictions, and I tend to think that this algorithms are ...
11
votes
4answers
422 views
Shortest number of editing move between two words
I am looking for a data structure and an algorithm to compute the minimum number of changes required to transform one word into another, given the two words as inputs, where the only allowed changes ...
8
votes
3answers
717 views
Are vertex colourings--in a sense--edge colourings?
We know that edge colourings of a graph $G$ are vertex colourings of a special graph,
namely of the line graph $L(G)$ of $G$.
Is there a graph operator $\Phi$ such that vertex colourings of a graph ...
