graphs

  1. greedy algorithms - minimizing total payment

  2. How to deal with cost variation in a dynamic graph when applying Dijkstra

  3. A path modification problem in directed graphs

  4. Find path in graph that is always having positive weight

  5. How does Bellman-Ford find Negative Weight Cycles

  6. Is there an algorithim to construct a graph with an even number of vertices, and each vertex has k edges?

  7. Predecessor-subgraph property

  8. How to find a minimum cut of a network flow?
  9. Cycles in undirected graph: reducing to minimum
  10. Uniformly randomly generating an "unlockable" graph

  11. Boruvka MST algorithm using doubly linked lists

  12. Visiting all train stations

  13. When will DFS create a spanning tree?

  14. Does the A* algorithm visit every node?
  15. Feedback Vertex Set with vertex partitions?

  16. Finding k-nearest neighbors to a set of nodes in a large graph
  17. Map overlay, any algorithm for face updating step?

  18. Is this problem just an application of traveling salesman? If not is it some other already "solved" problem?

  19. Deleting nodes from graph so that they can be separated by a straight line

  20. What would Dijkstra's shortest path algorithm complexity be with the following data structure?
  21. How do I find depth and height of all nodes in a bounded semilattice?

  22. AI: Heuristic function A* search

  23. Is there such a thing as an "or" case in a dependency graph?

  24. Finding subgraph problem

  25. How does make/scons manage dependency graph and figure out which file need to be recompiled?
  26. k-server problem with variable k
  27. Enumerating path variations
  28. How to define a language for an independent set problem of a graph?

  29. Does MST exclude the edge belongs to the cycle of the graph?
  30. Maximize the number of edges in subgraph

  31. Applying graph "adjustment" algorithms to Elo rating system
  32. Greedy max k-cut approximation algorithm

  33. Graph coloring decision problem NP-complete
  34. Find a simple path through a graph, vising as many vertices in Z as possible
  35. Graph Coloring Problem : How to Think About Algorithms Exer 1.6.2

  36. Show that Knapsack-like problem on directed graph is NP-hard

  37. Algorithm to find individual, closed groups of lines in a large set of connected lines

  38. Modeling an inequality problem to a graph

  39. Algorithm to find maximum weight from vertex a to b

  40. Correctness of Strongly Connected Components algorithm for a directed graph

  41. How to find an optimal sequence of matching
  42. What is the exact algorithm to find maximum clique of a given unit disk graph?
  43. Mother vertex of a graph

  44. NP-hardness of existence of spanning tree with given maximal degree

  45. Finding optimum point that minimizes maximum distance
  46. Determine if a vertex is a part of a cycle in O(m+n) complexity
  47. Decomposing a graph into paths
  48. Reduction of graph chromatic number to hypergraph 2-colorability

  49. Biggest number of components in a graph?
  50. Turn MST of G to MST of G'

  51. how do we know the initial and the terminal vertex on graph?
  52. What is the most efficent single-source shorthest path algorithm in unweighted directed grid graph?

  53. Counting the number of connected components in a dynamic plane graph
  54. For a cycle with $n$ vertices, how many distinct chords are possible?

  55. Appropriate graph clustering algorithm

  56. Questions on shortest path and minimum spanning tree

  57. Best complexity results for updating strongly connected components with incremental arc additions and deletions

  58. Algorithm for 3-object matching

  59. Connection betweem treewidth and feedback vertex set

  60. Finding all unique paths from a source to a sink in a specially-formed DAG
  61. Testing if a given DAG is a lattice
  62. Proving a factor 2 performance guarantee for a greedy minimum cardinality vertex cover algorithm (Exercise)

  63. Number of nodes of height $h$ in a heap or almost complete binary tree

  64. When are edges adjacent?
  65. Extending ordered tree edit distance to DAGs

  66. Least steps to find which ends of cables belong to each other

  67. Definition of a reachable ancestor (Skiena TADM 2nd ed section 5.9.2)

  68. Proving that vertex labeling is NP-complete
  69. Find a node with maximum distance from given node in a tree
  70. Dijsktra's algorithm applied to travelling salesman problem

  71. Why every point is in exactly one pair in Well Separated Pair Decomposition(WSPD)
  72. Solving a system of constraints
  73. Distance vector in a weighted graph

  74. how to prove original intervals and canonical form of intervals have the same interval graph

  75. How do I solve this graph with Dijkstra's Algorithm?
  76. Finding maximum-cardinality independent set with a particular oracle

  77. Bipartite graph matching with multiplicities

  78. Having trouble proving vertex cover greedy algorithm
  79. Vertex deletion to perfect matching

  80. Rule-based targeting algorithm
  81. How many times does a pair of numbers co-occur in a list?

  82. Finding a string with some specified hamming distances from other strings

  83. Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?

  84. How to prove that for a full binary tree $T$ there's a series of frequencies such that Huffman alg. will produce $T$?
  85. How to restore a broken minimal spanning tree?
  86. Merge Leaf labeled trees

  87. Increasing every starting edge by a constant, then the shortest path tree remains the same?

  88. Clustering based on weights of edges
  89. Find cut vertex in tree with constraint on the size of largest component
  90. Reconstruct graph of N edges from a matrix of shortest pair distances (N*N) (i.e. result from Floyd-Warshall algorithm)

  91. What algorithm to use for this kind of routing optimization?
  92. Algorithm for finding cliques

  93. Algorithm - True shortest path for triangulated 3d-surface

  94. How consistent heuristics guarantees A* optimality without adding same node to the frontier twice or more
  95. Is it possible to reconstruct graph if we have given matrix of shortest pairs

  96. Converting a digraph to an undirected graph in a reversible way
  97. Hat Distribution Problem

  98. Develop a winning strategy for a game

  99. Is this statement true: " A tree whose score can't be improved by adding an edge and removing one is MST."?

  100. Transitive reduction of DAG