graph-theory

  1. Distance between $u$ and $v$ is the same as distance between $v$ and $u$ in a transposed graph?

  2. Subgraph of paths of a graph has cycles?
  3. Question about Complete partially Directed Acyclic Graph

  4. Why line graph is a proper subclass of claw-free graph?
  5. Is this problem just an application of traveling salesman? If not is it some other already "solved" problem?

  6. Best game rating algorithm for punctual games with rating+variance : is Glicko-2 satisfying?
  7. How to find a Graph Embedding given a metric space?

  8. Question regarding terminology used to describe Benes networks
  9. How to find total number of minimum spanning trees in a graph with n edges?

  10. Applying graph "adjustment" algorithms to Elo rating system

  11. Do we need visited flags when applying BFS on a tree?
  12. What is the formal way to prove this is still a minimum spanning tree?

  13. Machine learning for labelling a directed graph
  14. Where is the second face in a graph with 3 nodes?

  15. Understanding time complexity of a while loop that will look over all vertices and edges

  16. Find longest path in graph with N nodes and N edges

  17. Finding if there exists a vertex that can be reached by all other vertices
  18. Removing vertices that belong to a given set from a graph
  19. Do we generally store the degree of each vertex in the linked list implementation? if not, why?
  20. Minimum path cover--- Disjointed paths with minimum total number of edges

  21. Finding shortest path involving additional restrictions

  22. Given an oriented graph, return true if paths have a specified length

  23. Algebraic (spectral) algorithms for the minimum spanning tree problem

  24. Number of automorphism for clique of 6 vertices minus two non adjacent edges

  25. Knight's Tour Parberry algorithm: 4 knight's tour merge procedure

  26. Minimum capacity cut reduction from digraph with two edge weight sets

  27. Multi-trip travel salesman problem

  28. P = NP and Polynomial Reductions

  29. Why does A* fail to find the fastest path when it reaches the goal?

  30. Eigenvalue computation for large graph

  31. Fitness model for scale free networks
  32. Decreasing the weight of one edge of minimum spanning tree, prove the MST is unchanged

  33. Enumerate all (n-1) edge disjoint perfect matchings in complete (undirected) graphs

  34. What is the significance of negative weight edges in a graph?

  35. Recalculating dominance after changing the entry node

  36. Longest-Path Layering algorithm

  37. Shortest path on a dynamic multigraph
  38. Space complexity for connectivity problem with given graph diameter

  39. Do the edges in the least cost paths given by Bellman-Ford algorithm produce a spanning tree?

  40. Finding The Shortest Path In Scotland Yard?

  41. Is there a difference between perfect, full and complete tree?
  42. Is there a reasonable algorithm to generate a certain "independent clique graph" with minimal vertices?
  43. Generalized Geography problem time and space complexity
  44. Reversing topo-order of the original graph instead of the topo-order of the transposed graph?

  45. Finding arcs between strongly connected components

  46. How to efficiently compute the most isolated point?
  47. Find a path that contains specific nodes without back and forward edges
  48. How to deal with cost variation in a dynamic graph when applying Dijkstra

  49. What is a reducible flow graph?
  50. is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

  51. Dependency graph with general (AND/OR) dependencies

  52. Printing all paths of a tree and sorting the weight of edges
  53. Complexity of increasing the radius of a graph
  54. Covering a complete graph with n copies of an arbitrary graph: NP-complete?

  55. minimum subgraph whose cost is greater than a predefined threshold
  56. Graph Algorithm (Modification on Dijkstra?) : Tech Interview

  57. How can I partition a graph such that as few edges as possible cross partition boundaries?
  58. Pruning a powerset based on a graph

  59. Insertion Heuristics to the TSP Problem
  60. Greedy Heuristic for the Traveling Salesperson Problem

  61. A Question about a Question related to Graph Theory and Maximum Flow

  62. The Number of Paths in a Directed Graph

  63. Algorithm to compute shape and volume of polyhedrons (polytope) formed by finite planes
  64. Partition a graph such that each subgraph fits the machine constraint
  65. Equivalence between two definitions of Tree width

  66. Where can I find a data set of graphs with known domination numbers?
  67. How to find the path for the most negatively-weighted cycle which goes through a specific source node?

  68. What graph theory algorithm(s) would help solve this problem?

  69. Proving a factor 2 performance guarantee for a greedy minimum cardinality vertex cover algorithm (Exercise)

  70. Graph families with high $k$-community

  71. How to find m directed paths connecting the maximal number of vertices in an unweighted directed acyclic graph?

  72. Looking for a good algorithm to divide the nodes of a complete graph into groups
  73. Maximum number of not overlapping cycles in an undirected graph

  74. Assign team members to groups to maximize outcome
  75. What does a wedge in a graph look like?

  76. How is reachability reduced to order maintenance?
  77. Edge contraction in DAG
  78. Enumerating pairs of disconnected cliques in a graph
  79. Perfect matching in a bipartite regular graph in linear time
  80. Convert DAG whose transitive reduction is non-planar to a planar DAG with same transitive closure

  81. Size of flow in a flow network with a vertex in the middle

  82. Graph algorithm or framework for determining node affinity based on utilities
  83. Edge removal to convert a non-planar DAG to a planar DAG while maintaining reachability?

  84. Bipartite Perfect Matching "Assignment Problem" - finding an assignment of a particular weight

  85. Between every two MST's there's a series of "nearby" MST's

  86. Find all the cumulative sums in a DAG

  87. Two criteria for an edge to belong to all MSTs

  88. What is the maximum possible degrees of a vertex of an MST
  89. Remove parallel edges in a directed graph in linear time

  90. How to minimally extend a digraph such that all nodes are on a cycle?
  91. Complexity of Two problems graphs with cycle
  92. Complexity of the problem to determine if a spanning tree exists inside a connected graph

  93. Are all vertices within a strongly connected component with 2 or more vertices part of a cycle?

  94. Shortest Path using at most k colors
  95. Finding mergable groups in a directed graph

  96. Expander Graph - Is the following graph family an expander graph?
  97. Maximum independent set in progressive k-partite graphs

  98. Would it be feasible to use a breadth first search algorithm for finding a solution to the 3x3x3 rubiks cube?

  99. Determine if a vertex is a part of a cycle in O(m+n) complexity
  100. Minimum sub-tree of a graph that covers each color at least once