Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.

learn more… | top users | synonyms

0
votes
0answers
20 views

A bound for the minimum vertex cover of scale-free graphs

For a complete graph, the size of minimum vertex cover is $n-1$. I was wondering whether there exist an upper bound (or an expected value or upper bound) for the size of minimum vertex cover for ...
4
votes
0answers
29 views

Model Join calculus as hypergraphs

I'm not sure if this is the right site to ask, but I couldn't find a another one. Some time ago I found out about the join calculus. It is based on constructs called joins to support concurrency. For ...
1
vote
1answer
50 views

Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded

Given an undirected graph $G=(V,E)$, two distinct vertices $s,t\in V$, a weight function $f:E \to \mathbb{N}$, and a constant $M\in \mathbb{N}$, does there exist a pair of edge disjoint paths ...
4
votes
1answer
126 views

Complexity of the decision version of determining a min-cut

I was wondering what the complexity of the following problem is: Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$. Question: Is there an $s$-$t$ cut of capacity at most ...
-1
votes
0answers
19 views

k-maximally link disjoints paths with weight constraints

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
3
votes
0answers
81 views

Maximum local edge connectivity [migrated]

For a simple graph, the local edge connectivity of vertices $x,y$ where $x\neq y$ is $\lambda(x,y)$ and defined as the maximum number of edge disjoint paths from $x$ to $y$. One can find this by a ...
0
votes
0answers
19 views

Are fat trees dynamic or static network topologies?

Is a fat tree topology a dynamic or static network topology? Because as far as I understood a binary tree is a static topology, but we have different stages for a fat tree. Are all multistage networks ...
0
votes
2answers
54 views

Can we construct a binary tree with width and height Θ(n)?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
0
votes
0answers
28 views

Number of Hamiltonian Path/Cycle Decompositions in Complete Bipartite Graph?

Does anyone know if there exists a paper or work about the Number of Hamiltonian Path/Cycle Decompositions in a complete bipartite Graph? I know of the Walecki Decomposition of a complete graph K_n ...
-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 ...
1
vote
0answers
27 views

Upper Bounds on Characteristic Path Length of Graphs

Characteristic (average) path length is defined here: http://cs.stackexchange.com/a/7538/20256 I want to establish upper and lower bounds on the CPL for a graph of $n$ vertices, and any positive ...
5
votes
1answer
320 views

Why is the complexity of negative-cycle-cancelling $O(V²AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
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 ...
0
votes
1answer
52 views

Preserving connectivity from a vertex by edges deletion

Given a connected graph $G$ and a vertex $v$, is it polynomially solvable to find a maximal cardinality set of edges incident to $v$, which deletion (still) leaves vertex $v$ to be connected with all ...
5
votes
2answers
152 views

Adding a node between two others, minimizing its maximum distance to any other node

We are given an undirected graph weighted with positive arc lengths and a distinguished edge $(a,b)$ in the graph. The problem is to replace this edge by two edges $(a,c)$ and $(c,b)$ where $c$ is a ...
6
votes
0answers
79 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 ...
7
votes
4answers
202 views

Recovering a point embedding from a graph with edges weighted by point distance

Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the ...
2
votes
2answers
52 views

Search in a partial ordering defined by tuples of numbers

This is a graph theory and partial ordering problem. Consider a set of triples {(di,ai,ci)}i=1...N, which specify edges between two nodes A and B, d denotes a departure time, a an arrival time and c a ...
1
vote
1answer
56 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
70 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 ...
2
votes
0answers
24 views

In case of a given graph , Is that possible to build trapezoidal map in linear time

[This regarding to Computational geometry in CS] Let's say that I have a graph G which contains v vectices and e edges, For instance a veronoi diagram VD(G). I'd like to build a trapezodial map out ...
5
votes
1answer
58 views

Easy infinite subclass of cubic graphs for Hamiltonian cycle problem

I know that Hamiltonian cycle problem is $NP$-complete for 2-connected planar bipartite cubic graphs. I'm interested in non-trivial infinite subclass of cubic graphs where the Hamiltonian cycle ...
4
votes
1answer
35 views

First Order interpretation of arbitrary structures as a graph

I am currently trying to get some intuition on the concept of First Order reductions, and have come across this exercise question by Immerman, dubbed "Everything is a Graph". Given some arbitrary ...
-1
votes
2answers
59 views

What is theory behind graphs relations? [closed]

I have been trying to understand, what is the actual meaning of 2 graphs being: Symmetric Transitive Reflexive A graph being a subgraph of another graph And ...
1
vote
0answers
159 views

What edges are not in any MST?

This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed. Consider a weighted undirected ...
-1
votes
1answer
117 views

Symmetric TSP optimization by removing nodes

Please tell me if my next optimization can work: I have symmetric, weighted, undirected graph, where it is knowen that the optimal tour, that visit all the vertices exactly once and return to the ...
3
votes
3answers
4k views

Why can't DFS be used to find shortest paths in unweighted graphs?

I understand that using DFS "as is" will not find a shortest path in an unweighted graph. But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? ...
4
votes
1answer
146 views

Complexity of Hopcroft-Karp

I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where ...
3
votes
0answers
124 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
85 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
61 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
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 ...
3
votes
1answer
28 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 ...
1
vote
2answers
174 views

Spanning Tree - Equivalent Properties

I am working on the following problem: Suppose that $T$ is a spanning tree of a graph $G$, with an edge cost function $c$. Let $T$ have the cycle property if for any edge $e' \not \in T, c(e') ...
7
votes
1answer
107 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 ...
8
votes
5answers
577 views

Standard or Top Text on Applied Graph Theory

I am looking for a reference text on applied graph theory and graph algorithms. Is there a standard text used in most computer science programs? If not, what are the most respected texts in the ...
2
votes
1answer
43 views

Choose $n/2$ vertices and guarantee $3/4$ of edges are accounted for proof

Give a polynomial-time algorithm that finds ceil(V/2) vertices that collectively account for at least three-fourths (3/4) of the edges in an arbitrary undirected graph. The algorithm I have come up ...
1
vote
1answer
55 views

To show that a graph-problem is in $L$ or $NL$

Consider the following problem: $$A=\left\{ (G(V,E),s,t)\mid\text{conditions 1, 2, 3 and 4 hold} \right\}$$ $G$ is a directed graph. $s,t\in V$. There is a simple path from $s$ to $t$ (a simple ...
1
vote
2answers
66 views

if (dis)proving a conjecture on graph theory can be done just by a counter example then can every (dis)proof be mapped actually to a counter-example?

Suppose we have a conjecture on graph theory that can be (dis)proved by means of a counter example, then, is it true that every alternative (dis)proof of the conjecture can be mapped to a counter ...
3
votes
1answer
83 views

Graph Theory Handshaking problem

Mr. and Mrs. Smith, a married couple, invited 9 other married couples to a party. (So the party consisted of 10 couples.) There was a round of handshaking, but no one shook hand with his or her ...
0
votes
1answer
115 views

Find the number of topological sorts in a tree

Find the number of topological sorts in a tree that has nodes that hold the size of their sub-tree including itself. I've tried thinking what would be the best for m to define it but couldn't get ...
1
vote
1answer
48 views

Choosing spanning trees to maximise node connectivity

Given: n variables in X, and m sets of variables where each set, Ci contains a subset of X. I am trying to generate the graph G = (X, E) by picking the edges in E given the following constraints. ...
0
votes
2answers
35 views

Embedding a general planar graph into a grid

I have here a little problem with my homework, and would appreciate some direction. I am attempting for some time now to show that every planar graph is embeddable into a grid (As large as needs be). ...
5
votes
1answer
110 views

Is Hamiltonian path NP-hard on graphs of diameter 2?

Let $G$ be a graph of diameter 2 ($\forall u,v\in V: d(u,v)\leq2$). Can we decide if $G$ has Hamiltonian path in poly time? What about digraphs? Perhaps some motivation is in place: the ...
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 ...
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 ...
5
votes
1answer
116 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 ...
6
votes
1answer
54 views

Expected number of maximal cliques in $G(n,p)$

The $G(n,p)$ random graph model creates graphs with $n$ vertices and each possible edge exists independently with probability $p\in (0,1)$. Much is known about the (expected) size of a largest ...
0
votes
0answers
37 views

Proof of shortest-paths optimality conditions

I am struggling with understanding the proof of shortest-paths optimality conditions. Let $G$ be an edge-weighted digraph. Then values in $distTo[]$ are the shortest path distances from $s$ iff: ...
-1
votes
1answer
51 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 ...