graph-theory

  1. Colouring the graph

  2. Filling a 3x3 board with connected tiles

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

  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. Dependency graph with general (AND/OR) dependencies
  8. Visiting all train stations

  9. What is the exact definition of undirected graph, directed graph, unidirectional graph, bidirectional graph?

  10. When will DFS create a spanning tree?
  11. Feedback Vertex Set with vertex partitions?

  12. Question about Complete partially Directed Acyclic Graph

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

  14. Intuition behind the max-flow min-cut theorem

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

  16. Finding subgraph problem

  17. Question regarding terminology used to describe Benes networks
  18. Minimal hitting sets of an interval hypergraph
  19. Longest path in a DAG: source to sink?
  20. Maximize the number of edges in subgraph
  21. Applying graph "adjustment" algorithms to Elo rating system

  22. Prove the crossing number of complete graph with 7 vertices is greater than or equal to 7

  23. How many edges can you add to the petersen graph without changing the crossing number
  24. Can Hall's theorem be applied to scheduling problems?

  25. Find a simple path through a graph, vising as many vertices in Z as possible
  26. Graph Coloring Problem : How to Think About Algorithms Exer 1.6.2

  27. Does a graph diameter equal to DFS tree depth?

  28. Decide if there is a sbugroup of edges in graph that every vertex meets exactly k edges from subgroup
  29. About the 'trick' for finding the diameter of an graph in $O(n^2)$
  30. Reducing Clique to Independent Set

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

  32. How to find an optimal sequence of matching

  33. Mother vertex of a graph

  34. Maximum Independent Set of a Bipartite Graph
  35. Finding optimum point that minimizes maximum distance
  36. Determine if a vertex is a part of a cycle in O(m+n) complexity

  37. Decomposing a graph into paths

  38. Biggest number of components in a graph?
  39. Counting the number of connected components in a dynamic plane graph

  40. The heaviest induced subgraph problem

  41. For a cycle with $n$ vertices, how many distinct chords are possible?

  42. Best complexity results for updating strongly connected components with incremental arc additions and deletions
  43. Fitness model for scale free networks

  44. Complexity of feasibility of a certain weighted digraph problem

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

  46. When are edges adjacent?

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

  48. Prove longest path shares two points

  49. Dijkstra algorithm step in Introduction to Algorithms

  50. How to find spanning tree of a graph that minimizes the maximum edge weight?

  51. Bipartite graph matching with multiplicities
  52. Vertex deletion to perfect matching

  53. brute-force canonical labelling of a simple graph

  54. Is there a reasonable algorithm to generate a certain "independent clique graph" with minimal vertices?
  55. Increasing every starting edge by a constant, then the shortest path tree remains the same?
  56. Infinite sequence of graphs

  57. Reconstruct graph of N edges from a matrix of shortest pair distances (N*N) (i.e. result from Floyd-Warshall algorithm)
  58. Algorithm - True shortest path for triangulated 3d-surface

  59. Is it possible to reconstruct graph if we have given matrix of shortest pairs

  60. Combinatorics: how many ways can we mark nodes in a DAG as black or white, if every node downstream of a black node is also black?

  61. Converting a digraph to an undirected graph in a reversible way

  62. Odd path minimum weight median in a DAG

  63. traverse direct graph with multiplicative edges
  64. Algorithm for finding cycles in a hypergraph

  65. Graph of MSTs of a graph - 2 msts connected if differ by 1 edge - is this single-component?

  66. How to solve this matching problem in one step
  67. Find a particular connected graph within a complete graph keeping all vertices
  68. Any way to find a 3-vertex cycle in a graph using an incidence matrix in O(nm) time?

  69. What are barriers to Genetic Programming with cyclic graphs

  70. Shortest Path for colored-edge directed graph between vertices s and t

  71. Finding multiple shortest path trees from an undirected, weight graph

  72. How to draw lines in fewest strokes?
  73. Matching items from two sets for maximum value
  74. Shortest cycle containing specific points

  75. Why are Oracle call instances bounded in the definition of FPT Turing reductions?

  76. Matrix of paths in a graph

  77. Is there a polynomial algorithm for optimal sorting on trees?

  78. What is the relationship between minimum sized vertex covers and complete graphs?
  79. Find the minimal cost of a tour which visits $k$ nodes in tree-like graph

  80. cascading behavior in networks
  81. Graph isomorphism problem for labeled graphs
  82. What is the significance of negative weight edges in a graph?

  83. Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?

  84. If two vertices point to one another in a directed graph, is the graph then considered cyclic?

  85. Understanding characterizations of Matching on Graphs
  86. Graph Algorithm (Modification on Dijkstra?) : Tech Interview
  87. Planar graphs of bounded degree: mixing time = cover time?

  88. "Breadth course" problem – find maximum independent set given all maximal cliques

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

  90. Minimum Number of People Such That No Two People Know the Same Two People

  91. Eigenvector centrality of graph with negative weights
  92. Minimal Spanning Tree With Double Weight Parameters
  93. Minimum number of edges to add such that there are no bridges on a tree
  94. Longest path in directed graph cyclic graph where each node has one children
  95. Finding the shortest path in non-complete node-weighted graph

  96. Not able to devise a concrete solution for the given graph query

  97. Find minimum time path between two nodes

  98. Expected distance between tree nodes
  99. Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

  100. Tree with branching factor 1