# Tagged Questions

17 views

### Explanation of LexBFS

I trying to understand the LexBFS algorithm, which is an algorithm for ordering the vertices in an undirected graph. Because I am not a computer science student, I am not able to understand the ...
26 views

### Algorithmically constructing graphs with specified degrees

In graph theory books there are lots of problems similar to these: Construct a graph of 7 vertices with exactly 5, 2, 1, 1, 1, 1, 1 degrees Prove or disprove that there is graph of 4 vertices with ...
32 views

### Map Subgraph Ismorphism Problem to SAT Problem

The Subgraph Isomorphism (SI) problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H. I want to ...
89 views

### Mathematicly Untangeling Untangle.

I have a new addiction, I play Untangle to often, and i am wondering what is the mathematics behind it. some free games: (but be warned highly addictive) Javascript: ...
31 views

### Maximum independent set problem

I need to study about the maximum independent set problem in graph theory. I need to study the $P_t$ free graphs and many other such variants and look up their maximum independent set characteristics. ...
15 views

22 views

### Weighted Set covering problem with a fixed number of colors

I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost. I have a fixed number of colors, C = {1 , 2, ...
639 views

### Undirected graph 1 degree checking

Given an undirected graph, which consists of n vertexes and m edges. Provided we can delete edges from the graph. Now we want to check is it possible to delete edges in the graph so that the degree of ...
78 views

### Which algorithm is this?

I am studying for the exams and I am looking at my notes, where I came across with an algorithm, but there is no title, so I don't know which algorithm it is and it doesn't also exist in my textbook. ...
34 views

### Does every simple cycle contain at least one back edge?

Soppose we have an udirected, connected graph. Apply the DFS algorithm to find back edges of this graph. Now, I have found a lecture notes saying following : Each back edge (i,j) defines a cycle. A ...
51 views

### Minimum number of elements needed from n sets

Suppose that we have n sets. They may or may not have common elements. How can we find the minimum number of elements that we should pick so that we have at least one element from each set? For ...
41 views

### Algorithm to partition a graph under constraints

What would be an algorithm to partition the vertex set of an undirected graph into 2 vertex disjoint subsets such that each vertex has at most $\left\lfloor\frac{d}{2} \right\rfloor$ no of its ...
62 views

### Graph isomorphism and existence of nontrivial automorphisms

Consider the following two algorithmic problems - one of determining whether two graphs are isomorphic and the other of determining if a graph has a nontrivial automorphism: (1) Decision problem: ...
17 views

### Improved approximation algorithm for maximum weighted matching

I've read the discussion here: http://stackoverflow.com/questions/5203894/a-good-approximation-algorithm-for-the-maximum-weight-perfect-match-in-non-bipar, and I have implemented the Drake and ...
66 views

### Bitonic Shortest Paths

A sequence is bitonic if it monotonically increases and then monotonically decreases, or if by a circular shift it monotonically increases and then monotonically decreases. For example, the sequences ...
35 views

### Modified Shortest Path Problem

Consider a directed, weighted graph $G=(V, E)$ where all edge weights are positive. You have one magic star, which lets you traverse one edge of your choice for free. In other words, you may change ...
24 views

The city has n districts and n - 1 bidirectional roads. We know that from any district there is a path along the roads to any other district. Let's enumerate all districts in some way by integers from ...
43 views

### Finding minimal number of vertices which connect a graph

I'm doing some graph theory studying on my own and I encountered a problem. I have a connected graph $G$ of $11440$ edges and an unknown number of vertices. What would be the best algorithm to find ...
I have been given $n$ points on a $2d$ plane. In terms of their $(x,y)$ coordinates. Now suppose I have to set, say firms, at these positions and the cost for building the first one is zero. For every ...