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
8 views

Performing Transitive Reduction via neighbourhood and strongly connected components

I am trying to learn(self-study, not homework) how to perform transitive reduction according to what what Prof. Leskovec explains in section 10.8.6 in Mining Massive Datasets. The book is free to ...
4
votes
0answers
30 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 ...
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 ...
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 ...
-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 ...
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
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 ...
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. ...
-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
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 ...
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 ...
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
80 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 ...
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 ...
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 ...
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 ...
5
votes
2answers
153 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 ...
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 ...
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 ...
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 ...
-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 ...
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
125 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
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 ...
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
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 ...
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
84 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
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). ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
4
votes
1answer
67 views

Does spectral graph theory say anything about graph isomorphism

Is there research or are there results that discuss graph isomorphism in the context of spectral graph theory? Two known theorems of spectral graph theory are: Two graphs are called isospectral or ...
0
votes
2answers
71 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
1answer
43 views

For a flow network, is it possible to show that there always exists a maximum flow which would assign integer values to all the edges? [closed]

Is it possible to prove that for a flow network, there always exists a maximum flow which assigns an integer value to every edge?
7
votes
1answer
135 views

Research in Graph Theory versus Graph Algorithms

I have a very generic question to ask. It is related to research. I'm interested in Graph theory. I have done a course in it. I have done some topics related to both graph theory as a point of ...
0
votes
0answers
83 views

Example of graph with exponential many s-t minpaths and min cuts

I am trying to find a graph in which both s-t minpaths and min cuts are exponential. Individually I found examples in which s-t minpaths and s-t min cuts are exponential. Can some one provide me an ...
0
votes
2answers
41 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 ...
3
votes
2answers
104 views

Shortest path in weighted(positive or negative) undirected graph

I have to find an algorithm that finds the SSSP (single-source shortest path - shortest paths from one source vertex to all other vertices) on a weighted undirected graph. If there are 2 different ...
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 ...