graph-algorithms

  1. How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?
  2. Minimal Cost of Eulerian Path

  3. Counting the number of connected components in a dynamic plane graph
  4. Why isn't the Charikar algorithm for finding the densest subgraph optimal?
  5. Unbalanced connected partition

  6. What are graph grammars?

  7. Number of maximally different DAG's in a digraph?
  8. Vertex deletion to perfect matching
  9. How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0?

  10. Are query-dependent ranking algortihms for web search doomed to be impractical?

  11. What are some techniques for "balancing" a tree beside heavy-light and centroid decomposition?
  12. Complexity of finding semi-ordered Eulerian tours in a 4-regular graph

  13. Cluster Assignment in the Stochastic Block Model

  14. One Generalization of Graph Isomorphism Problem

  15. Determining ties in random network centrality rankings?
  16. \alpha-path on Euclidean graphs
  17. Algorithm finding path with maximal ratio of white vertices
  18. Decomposition of edges of eulerian graph into maximum number of cycles
  19. Algorithm for computing unordered tree edit distance
  20. Optimizing Maximum Weighted Matching (Edmonds Blossom)
  21. Complexity consequence of logarithmic boolean width of co-bounded degree graphs?

  22. Transitive Closure of Weighted Random Graphs?

  23. Finding k shortest Paths with Eppstein's Algorithm
  24. Modifying Edmonds' Blossom Algorithm

  25. Clique cover problem
  26. Max weight travel on a graph with deadline
  27. Graph factors of maximum weight
  28. Max-weight connected & co-connected subgraph problem

  29. What is known about learning a maximal independent set in a (very) sparse graph?

  30. Efficiently computing the union of all minimal unsatisfiable constraint sets in a first-order unification problem
  31. Does a weighted graph have a path with weight zero?

  32. Hard problems for bounded vertex cover
  33. Approximating the Radius of a (Dense) Graph

  34. A conceptual question regarding hardness proofs by reduction

  35. Complexity status of restricted k-clique

  36. Fastest way to find an s-t min-cut from an s-t max-flow?

  37. Solving a "tree-equation"?
  38. Restricted k-set cover is in NL or L

  39. Efficient update of reachable set of a node in a digraph

  40. How to partition a graph while minimizing the count of intra-edges?

  41. k-Vertex Cover problem is in NC_1 or AC_0
  42. Vertex Cover applications in the real world
  43. Log space algorithms for modular decomposition tree

  44. Reachability in Dynamic Line Graph

  45. What is the computational complexity of "solving" chess?

  46. Maximal non-reducible vertex cover of a graph

  47. parametrized logspace algorithm for k-dominating set for planar graphs

  48. Can Lexicographic BFS be implemented in logspace?

  49. How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming?
  50. 2FA state complexity of k-Clique?
  51. Paper regarding the complexity of the longest path problem on weighted directed graphs of bounded treewidth

  52. Deterministic Parallel algorithm for perfect matching in general graphs?

  53. Algorithms for finding all cliques of a given degree in a graph

  54. Optimal polynomial time algorithm to determine if a random graph is $k$-colorable
  55. Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices
  56. Is there a better than brute-force solution to the shortest simple path problem?

  57. Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs
  58. Fastest known deterministic algorithm for the undirected Graph Isomorphism problem

  59. Embedding a graph with specified edge lengths in d-dimensional space
  60. Looking for a list of algorithms that are more efficient for an outerplanar graph than for an arbitrary graph

  61. Finding almost minimum cycle

  62. Computing mTSP in a k-complete weighted graph
  63. What can i learn about a graph about which only certain properties are known

  64. Combinatorial Independent set Algorithms for sub-classes of perfect graphs

  65. Complexity of counting the number of edge covers of a graph
  66. Hardness of Subgraph isomorphism problem for sparse pattern graph
  67. Efficient enumeration of the reachable leaves of nodes in a polytree

  68. Computational Complexity of cycle double cover

  69. Finding minimum weight $k$ cliques in a complete graph

  70. find the densest subgraph of size k

  71. Examples of "Sandpile" TSP Instances
  72. zero-sum path problem on a digraph

  73. Reachability on DAG (best-known algorithm)

  74. Average of a variable over point pairs within a given distance in a point set in Cartesian space
  75. questions on implications Babais quasi P time graph isomorphism result

  76. Generalizing linear interpolation to posets
  77. Online triangle counting

  78. Approaches for Theoretical Analysis of Estimates of Probability Distributions

  79. Bounded 0/1-knapsack with dependency constraints without limit
  80. Partition refinement in transition state systems (bisimulation contraction)
  81. A linear time algorithm for the all pair longest paths on a special kind of trees

  82. Finding a graph that minimizes the number of nodes for a given number of paths
  83. Nonstandard dual parametrization of graph problems

  84. Shortest cycle separator for biconnected planar graphs
  85. Number of bounded minimum vertex covers
  86. Random walk and mean hitting time in a simple undirected graph
  87. Max weight k-clique

  88. Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K
  89. Shortest distance problem with length as functions of time

  90. Program for computing Tree decomposition of a graph
  91. Travelling Salesman Problem where a subset of the nodes must be visited in a particular order
  92. Bidirectional A*: is an update of the distance estimation feasible while searching?
  93. Triangle arrangement problem

  94. Graph Isomorphism Algorithm of Vertex Transistive Graphs and other
  95. Dichotomy of the spectra of directed graphs

  96. Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known

  97. Longest path from every vertex in a tournament
  98. Number of reachable vertices in DAG for every vertex

  99. Fastest Algorithm for the Minimum Edge Covering Problem

  100. What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?