0
votes
1answer
34 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
97 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
39 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
249 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
37 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
28 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
81 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
84 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
58 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
134 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
28 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
98 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
33 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
152 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
24 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
98 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
39 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
45 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
120 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 ...
2
votes
4answers
124 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 ...
0
votes
1answer
155 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
98 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
97 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
71 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
235 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 ...
1
vote
1answer
67 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 ...
5
votes
1answer
126 views

Largest set of vertices that is larger than its set of neighbors

I am reading a unpublished paper describing an algorithm. In one step of the algorithm, there is a bipartite graph $G(X,Y,E)$, where $X=\{1,...,n\}$. For every subset $X' \subseteq X$, they define ...
-1
votes
1answer
44 views

Satisfying condition to be in minimum spanning tree of an edge (maximum weight)

Let G be a weighted undirected graph and e be an edge with maximum weight in G.Suppose there is a minimum weight spanning tree in G containing the edge e.Which of the following statements is always ...
1
vote
1answer
84 views

Finding edges with minimal weight sum, such that every simple cycle contain at least one edge

Given simple, udirected and connected graph with $n$ verticies. Every edge in this graph has some weight. I have to find (in polynomial time) a set of edges such that : 1.every simple cycle in ...
1
vote
1answer
55 views

What is this algorithm? Create a tree's equivalent hierarchical network

This question was originally posted here: http://stackoverflow.com/q/20735339/2305618 I am surely not the first to have implemented code to perform the following graph transformation. But try as I ...
9
votes
0answers
70 views

Finding an st-path in a planar graph which is adjacent to the fewest number of faces

I am curious whether the following problems has been studied before, but wasn't able to find any papers about it: Given a planar graph G, and two vertices s and t, find an st-path $P$ which minimizes ...
0
votes
1answer
72 views

Find a diffrent minimal spanning tree for a graph

For my homework I have a problem that I can't solve and it makes me wonder about 2 different MST: Let $G=(V,E)$ be a graph that has a minimum spanning tree $T$. I want to find another minimum ...
1
vote
1answer
171 views

Reducing from Hamiltonian Cycle to Subgraph Isomorphism

I am reading Subgraph isomorphism problem I am having trouble understanding how they prove that the subgraph isomorphism problem is NP-Complete using the Hamiltonian cycles problem in the article. ...
3
votes
2answers
169 views

Minimum spanning tree and its connected subgraph

This problem is from the book Algorithms, Chapter 5: Greedy algorithms. In case of being closed as a duplication to that in Minimum Spanning tree subgraph, I will first make a defense: The accepted ...
0
votes
0answers
16 views

Why generally to find a Euler cycle is easier than Hamilton cycle for the same set of nodes? [duplicate]

To find a Hamilton cycle is a NPC problem, but Euler is not. Considering one can always transform the vertex as edge or vice versa conceptually. Then the vertex can be used to describe the information ...
1
vote
1answer
129 views

Widest path algorithm steps [closed]

I need to compute the bottleneck shortest paths from s to all vertices of a graph by modifying the Dijkstra’s algorithm. I found this explanation on Wikipedia(Link to Wikipedia) but I would appreciate ...
-2
votes
1answer
134 views

Modifying Dijkstra’s algorithm to favor the path with least amount of edges

I need to modify the Dijkstra's algorithm to get the shortest path in a directed graph and get the one with the least amount of edges if there are equal paths. I am thinking to add another data ...
4
votes
3answers
138 views

Algorithm to Group Vertices of Graph

Given is the following graph which is logically divided into layers (with Dijkstra's shortest paths algorithm): ...
3
votes
0answers
81 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
9
votes
3answers
126 views

Wiring Length Minimization

My Problem is like this: I have a physical layout represented as a graph. The Nodes represents hooks/ducts where a wire can anchor and Edges are the possible connection between 2 nodes from where ...
3
votes
2answers
2k views

Is it possible to modify dijkstra algorithm in order to get the longest path? [duplicate]

Is it possible to modify Dijkstra´s algorithm in order to get the longest path from $s$ to $t$ ?. My intuition says that I´ll need a different algorithm entirely. Finding the longest path is the ...
3
votes
2answers
265 views

CNF Generator for Factoring Problems

I've been reading these: Fast Reduction from RSA to SAT CNF Generator for Factoring Problems (Also have C code implementation) I don't understand how the reduction from FACT to $3\text{-SAT}$ ...
0
votes
1answer
85 views

Symmetric TSP optimization by removing nodes

I have a nice idea to optimize TSP by removing nodes, its going to be hard for me to explain my self, so please be patient with me and try to understand what I am saying. I have a symmetric(the ...
0
votes
0answers
52 views

Saturating all augmenting paths with the minimum edge capacity in max flow

To find the maximum flow in a graph, why doesn't it suffice to only saturate all augmenting paths with the minimum edge capacity in that path without considering the back-edges? I mean, what is the ...
1
vote
1answer
128 views

Approximated TSP: weight of minimum spanning tree less than cost of the optimal tour?

In the chapter, Approximation Algorithms of Introduction to Algorithm, 3rd Edition, for the approximation problem Travelling Salesman Problem, the author proposes a approximation method that first ...
5
votes
2answers
291 views

Points-in-a-plane from HackerRank

I've been struggling with this problem for days now, making no progress: There are N points on an XY plane. In one turn, you can select a set of collinear points on the plane and remove them. Your ...
1
vote
0answers
85 views

Recalculate max-flow after removing edge with 1 capacity [closed]

So I have some graph, and I know what it's max flow is based of the Ford-Fulkerson Algorithm. With this information, I need to know how to find a new max flow when I remove an edge of this graph with ...
3
votes
1answer
608 views

Running Floyd-Warshall algorithm on graph with negative cost cycle

I am trying to find the answer to the following question for the Floyd-Warshall algorithm. Suppose Floyd-Warshall algorithm is run on a directed graph G in which every edge's length is either -1, 0, ...
2
votes
1answer
65 views

What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero?

Suppose we are given an M×N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero ...
7
votes
1answer
111 views

Approximation algorithm for Feedback Arc Set

Given a directed graph $G = (V,A)$, a feedback arc set is a set of arcs whose removal leaves an acyclic graph. The problem is to find the minimum cardinality such set. I want to find out about is ...