7
votes
0answers
87 views

Change in the distances in a graph after removal of a node

Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that, $$\operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G ...
0
votes
0answers
85 views

Dynamic distance from source in a directed graph (only incremental or only decremental)

At the beginning we have a directed unweighted graph of $n \leq 10^3$ vertices, and $m \leq 10^5$ edges, with some vertex being a source, and we perform updates and queries on it. An update is adding ...
-1
votes
1answer
104 views

Mininun changes required in a directed graph to make path from 1 to n

i have a directed graph. Basically, i have to find how many edges i need to change to opposite direction to make a path between 1 and n. So, i tried solving it by making the graph undirected and ...
3
votes
2answers
94 views

Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size

There is a complete graph $G$ with $n$ vertices and each edge has a distinct weight. Is there an efficient (not necessarily optimal) algorithm to select $k$ vertices from the graph $G$, such that the ...
6
votes
0answers
84 views

Graph isomorphism problem for graphs with colored directed edges

In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is ...
1
vote
1answer
57 views

Non-Approximate Dynamic All-Pairs Shortest Path algorithm for Undirected, Unweighted Graphs?

I am looking for an algorithm involving adding unweighted edges to an empty, undirected graph (with vertices) and then for each, updating the table of shortest paths. An example is if we have ...
3
votes
1answer
73 views

Finding independent sets so that all nodes are hit frequently

I have a problem, and I appreciate it if you could share your thoughts. Assume that I have a graph. Assume that I have $k$ iterations. I want to find only one independent set (IS) in the graph in ...
3
votes
0answers
128 views

Find shortest paths in complement graph

I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, ...
4
votes
1answer
87 views

Shortest-depth routing algorithm

This problem came up in a graph network routing context, it can be expressed as follows: Let $n, m > 0$ be integers. Find any smallest list of positive integers $\langle a_1, \cdots, a_k ...
1
vote
0answers
63 views

Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?

Assumptions: given a graph with N nodes, and two specific nodes A and B the graph is undirected and no edge has a negative cost there exists at least one Hamiltonian path with A and B as an end ...
3
votes
1answer
29 views

Iterative Byzantine consensus in directed graphs with unbounded malicious nodes

I've found many articles describing iterative procedures to reach Byzantine agreement on a graph (for instance http://www.crhc.illinois.edu/wireless/papers/icdcn14-vaidya.pdf or ...
3
votes
1answer
54 views

How to obtain a trilateration ordering in a graph?

In a sensor network graph $G = (V,E)$ $V = \{1,2,...,n\}$ is the set of sensors and the edge $(i,j)$ denotes that sensor $i$ and sensor $j$ are inside each other's sensing range. The weight of that ...
7
votes
1answer
111 views

The equivalence relations cover problem (in graph theory)

An equivalence relation on a finite vertex set can be represented by an undirected graph that is a disjoint union of cliques. The vertex set represents the elements and an edge represents that two ...
0
votes
1answer
42 views

Find longest path between two disjoint sub-sets of vertices $V_1, V_2 \subset V$ of a Graph

I have a homework question which I would appreciate some help with: Let there be a DAG $G=(V,E)$ with positive weights. For every two different vertices $v_1, v_2$ we will define $D(v_1, v_2)$ to ...
0
votes
1answer
55 views

Finding all (weighted) cycles through a given vertex

For a connected undirected graph $G$, given a particular vertex $v$, is there a known (efficient) algorithm to find all simple cycles in $G$ that contain $v$? In my case, I have weights for every ...
5
votes
1answer
119 views

Distance k-Dominating Set on a Tree

I don't consider myself very good at math, but nevertheless I enjoy solving optimization problems like the ones often asked in ACM ICPC (a college programming competition). I recently came across an ...
-1
votes
1answer
53 views

Number of Different AVL Tree

I studying the related question. http://stackoverflow.com/questions/13500560/number-of-ways-to-create-an-avl-tree-with-n-nodes-and-l-leaf-node but it's not so general. In-fact, We want to know ...
0
votes
2answers
75 views

Understanding Tiernan's Algorithm

I am currently working through Tiernan's paper, "An efficient search algorithm to find the elementary circuits of a graph" (published 1970), and I am stuck on point 3 of the following excerpt: The ...
0
votes
2answers
42 views

Given a graph, finding if a node has three adjacents from a node subset $N$

Given a graph $G = (V,E)$, assume that we have two disjoint vertex sets $N = \{n_1, n_2 ...\} \subset V$ and $P = \{p_1, p_2, ...\} \subset V$ such that $N \bigcup P \neq V$. I want to find if there ...
0
votes
1answer
37 views

reducing planar 3-colouring from 3-colouring

I was reading this and I'm trying to understand how one would formally describe reducing planar 3 colouring to 3 colouring. The link pretty much describes the process but understanding the ...
1
vote
2answers
62 views

Visit all vertices on directed graph

We are given a directed graph, the number of vertices and edges. We need to decide, whether there is a [starting] vertex where we can get started and visit all the vertices. You can revisit vertices, ...
-1
votes
1answer
36 views

Find MST based upon new definition

Redefine the weight of a spanning tree to be the weight of the maximum weight edge in the tree (i.e. the weight of the tree is no longer the sum of the weights of all the edges in the tree, only the ...
2
votes
1answer
42 views

Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost

Given a fully connected graph $G$, suppose that we are searching for a simple path $P$ with a specific cost $c$. Is answering to that problem yes or no equivalent to subset-sum problem? What would ...
6
votes
1answer
78 views

Algorithm to find all acyclic orientations of a graph

I am working on acyclic orientations of undirected graphs and have the following questions: Given connected undirected simple graph $G$, how to find all possible acyclic orientations of $G$ ? What ...
0
votes
1answer
42 views

Recognizing interval graphs--“equivalent intervals”

I was reading a paper for recognizing interval graphs. Here is an excerpt from the paper: Each interval graph has a corresponding interval model in which two intervals overlap if and only if ...
2
votes
2answers
130 views

What is the difference between maximal flow and maximum flow?

What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a ...
2
votes
2answers
48 views

Reconstruct directed graph from list of ancestors for each node

I have a problem that I encountered that boils down to the following: Considered this directed graph I found on Google: I have the following information available to me ...
5
votes
4answers
280 views

Approximating NP-complete problems

Say that for a particular problem, e.g., the independent set problem, it has been shown that no polynomial-time algorithm exists to solve it. Could we get around this by finding an algorithm which ...
0
votes
1answer
43 views

Show that this algorithm does not work for determining convex polygons

Context Consider this algorithm. If the set $\{\angle p_ip_{i+1}p_{i+2} : i=0,...,n-1\}$ does not contain left and right turns, output "yes the polygon is convex"; otherwise, "no". My answer ...
1
vote
0answers
36 views

Question about spanning trees and creating them through BFS and/or DFS algorithms

The question is as follows: True or False: For every non-directed connected non-weighted graph and for every spanning tree T of the graph there exists a vertex v such that T is a DFS tree with the ...
0
votes
1answer
131 views

Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?

I am reading Prim's MST for the first time and wanted to implement the fast version of it . $m$ - The number of edges in the graph $n$ - The number of vertices in the graph Here's the algorithm ...
1
vote
0answers
99 views

Algorithm to determine a minimal cost graph [closed]

I'm trying to solve this problem: Given a collection of cities and the number of commuters between cities, design a network of roads for minimal cost where cost includes the cost of building the ...
2
votes
1answer
79 views

Similarity between two geometric shapes

I have two shapes in a 2D space, not necessarily convex, and I'd like to compare how similar they are. How can I define a robust distance metric to measure their similarity, and how can I compute it? ...
5
votes
3answers
248 views

Minimal spanning tree with degree constraint

I have to solve this problem: We have weighted $n$-node undirected graph $G = (V,E)$ and a positive integer $k$. We can reach all vertices from vertex 1 (the root). We need to find the weight of ...
2
votes
0answers
42 views

Steiner tree wiring problem

I’m trying to find an algorithm that can give me an approximate solution for a wiring problem that I have been asked to look at. I believe this is closely related to finding a node weighted Steiner ...
3
votes
3answers
182 views

How to implement graph search to solve Sudoku puzzle

My teacher pointed out to us during lectures that we could use Graph Search to help us solve Sudoku puzzles which has left me puzzled . I dont see how this is possible as Graph Search is mostly ...
3
votes
0answers
53 views

Maximum Weight Independent Set in Circular-Arc Graphs (Proof of A Lemma)

I am reading the paper: "Maximum Weight Independent Set Of Circular-Arc Graphs and It's Applications" (http://link.springer.com/article/10.1007%2FBF02832044). And I had a question regarding the proof ...
5
votes
3answers
187 views

Maximum number of matched vertexes in a one-to-many bipartite graph

I have a variant of bidding problem at hand. There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who ...
2
votes
1answer
42 views

Meyniel's theorem + finding a Hamiltonian path for a specific graph family

Let's say we have a directed graph $G = (V, E)$ for which $(v, w) \in E$ and/or $(w,v) \in E$ holds true for all $v, w \in V$. My feeling is that this graph most definitely is Hamiltonian, and I want ...
2
votes
1answer
109 views

Why is determining the size of a maximum independent set or a clique in P?

I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard. With respect to ...
1
vote
1answer
45 views

Proving the correctness of an algorithm, which computes the connectivity of a directed graph

Let $G=(V,E)$ be a directed graph. The connectivity of a graph is the defined as the cardinality of a smallest separator of $G$. A separator of $G$ is a subset $U$ of $V$, such that $G-U$ is not ...
0
votes
0answers
48 views

Need an upper bound for node degree

I have a social network in the form of an undirected graph $G = (V,E)$ with distinct non-negative integer keys. For each node $u \in V$, let the set $\Gamma(u) = \{ v \in V : (u,v) \in E \}$ be the ...
2
votes
1answer
572 views

Counting and finding all perfect/maximum matchings in general graphs

Recently i've been dealing with a problem that led me to the following questions: Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph? Is there a good algorithm ...
3
votes
4answers
203 views

Converting a digraph to an undirected graph in a reversible way

I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I ...
1
vote
1answer
201 views

find the minimum number of vertices in a directed graph from which the other vertices are reachable

In a directed graph i want to call bfs on some of the vertices so that all of the vertices will be met. (in other words all of the other vertices are reachable from these chosen vertices.) I want to ...
1
vote
0answers
160 views

Potential values of minimum cost maximum flow algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
1
vote
1answer
126 views

iterating over subsets by switching one element at a time

How do I iterate over all the $k$-element subsets of $\{1,2,\dots, n\}$ by switching one element at a time? 123 134 234 124 145 245 345 135 235 125 This comes ...
0
votes
0answers
111 views

Hopcroft–Karp algorithm time complexity

In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph: https://dl.dropboxusercontent.com/u/64823035/04569670.pdf The ...
0
votes
1answer
415 views

How to optimize Dijkstra's algorithm for a grid graph?

I'm trying to apply Dijkstra's algorithm to the Problem 83 on projecteuler.net. The problem reads: In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by ...
2
votes
1answer
115 views

Non intersecting paths in a graph

I'm trying to come up with a good algorithm for the following decision problem: Let $G=(V,A)$ be a directed graph and let $s,t \in V$. Are there at-least 2 non-intersecting paths from $s$ to $t$? By ...