Search results

Page title matches

• Graph traversal
  # [[Basic graph definitions]] # A [[Basic graph definitions|directed graph]] <math>G=(V,A)</math>.
  2 KB (314 words) - 19:06, 9 November 2014
• Bipartite graph
  [[File:Bipartite-graph.png|200px|thumb|right|A simple bipartite graph]] An undirected graph <math>G=(V,E)</math> is called '''bipartite''' if there is a partition of <
  2 KB (319 words) - 11:33, 13 October 2014
• Directed graph
  ...es in contrast to unordered pairs of nodes (called edges) in an undirected graph. An arc <math>a = (v, w)</math> is considered to be directed '''from''' <ma
  445 bytes (82 words) - 20:12, 17 November 2014
• Undirected graph
  68 bytes (8 words) - 00:32, 17 June 2015
• Basic graph definitions
  # A '''directed graph''' <math>G=(V,A)</math> consists of a finite set <math>V</math> of '''nodes # An undirected graph <math>G=(V,E)</math> consists of a finite set <math>V</math> of '''nodes'''
  15 KB (2,712 words) - 14:47, 16 May 2015
• Exhaustive graph traversal
  A [[Basic graph definitions|directed graph]] <math>G=(V,A)</math>.
  195 bytes (27 words) - 07:21, 3 November 2014
• K-partite graph
  An undirected graph <math>G=(V,E)</math> is called '''k-partite''', if there is a partition of For <math>k=2</math>, <math>G</math> is called [[bipartite graph]].
  536 bytes (96 words) - 19:53, 17 November 2014
• Lecture: Efficient Graph Algorithms
  5 KB (732 words) - 09:07, 13 February 2016
• Efficient Graph Algorithms:Gallery
  #REDIRECT [[Lecture: Efficient Graph Algorithms]]
  49 bytes (5 words) - 22:36, 13 October 2015

Page text matches

• Biconnected components
  # [[Basic graph definitions]] ...n and without loss of generality, we assume that <math>G</math> is [[Basic graph definitions|simple]].
  544 bytes (73 words) - 19:07, 9 November 2014
• Directed graph
  ...es in contrast to unordered pairs of nodes (called edges) in an undirected graph. An arc <math>a = (v, w)</math> is considered to be directed '''from''' <ma
  445 bytes (82 words) - 20:12, 17 November 2014
• Strongly connected components
  # [[Basic graph definitions]] A [[Basic graph definitions|directed graph]] <math>G=(V,A)</math>.
  429 bytes (58 words) - 19:07, 9 November 2014
• Exhaustive graph traversal
  A [[Basic graph definitions|directed graph]] <math>G=(V,A)</math>.
  195 bytes (27 words) - 07:21, 3 November 2014
• Minimum spanning tree
  # An [[Basic graph definitions#Directed and undirected graphs|undirected graph]] <math>G = (V,E)</math>, not necessarily connected. An [[Basic graph definitions#Forests, trees, branchings, arborescences|undirected tree]] <ma
  539 bytes (79 words) - 12:33, 16 June 2015
• Maximum spanning forest
  # An [[Basic graph definitions#Directed and undirected graphs|undirected graph]] <math>G = (V,E)</math>, not necessarily connected. An [[Basic graph definitions#Forests, trees, branchings, arborescences|undirected forest]] <
  540 bytes (79 words) - 18:03, 18 September 2015
• Graph traversal
  # [[Basic graph definitions]] # A [[Basic graph definitions|directed graph]] <math>G=(V,A)</math>.
  2 KB (314 words) - 19:06, 9 November 2014
• Bipartite graphs
  #REDIRECT [[Bipartite graph]]
  29 bytes (3 words) - 08:53, 5 October 2014
• Blocking flow
  # [[Basic graph definitions]] Let <math>G=(V,A)</math> be a directed graph, let <math>s,t\in V</math>, and for each arc <math>a\in A</math> let <math>
  1 KB (189 words) - 19:06, 9 November 2014
• Efficient Graph Algorithms:Gallery
  #REDIRECT [[Lecture: Efficient Graph Algorithms]]
  49 bytes (5 words) - 22:36, 13 October 2015
• Maximum branching
  # [[Basic graph definitions]] # A directed graph <math>G=(V,A)</math>:
  689 bytes (107 words) - 07:53, 8 November 2015
• Eulerian cycle
  ...asic graph definitions#Cycles|ordinary cycle]] in a directed or undirected graph that contains each edge/arc exactly once. # A directed or undirected graph is called '''eulerian''' if it admits a eulerian cycle.
  2 KB (307 words) - 20:57, 12 November 2014
• Maximum-weight matching
  # [[Basic graph definitions]] # An undirected graph <math>G=(V,E)</math>.
  2 KB (264 words) - 17:37, 6 December 2014
• K-partite graph
  An undirected graph <math>G=(V,E)</math> is called '''k-partite''', if there is a partition of For <math>k=2</math>, <math>G</math> is called [[bipartite graph]].
  536 bytes (96 words) - 19:53, 17 November 2014
• Cardinality-maximal matching
  # [[Basic graph definitions]] An undirected graph <math>G=(V,E)</math>.
  2 KB (305 words) - 09:51, 6 December 2014
• Min-cost flow problem
  # [[Basic graph definitions]] ...definitions#Directed and undirected graphs|simple, anti-symmetric directed graph]] <math>G=(V,A)</math>.
  2 KB (348 words) - 14:31, 1 December 2014
• Main Page
  === Graph Theory === * [[Directed graph]]
  4 KB (380 words) - 15:13, 30 November 2020
• Matchings in graphs
  ...teq E</math> of edges such that no two edges in <math>M</math> are [[Basic graph definitions#Adjacency, incidence, and degree|incident]]. # A path <math>p</math> in an undirected graph <math>G=(V,E)</math> is called '''alternating''' with respect to some match
  7 KB (1,194 words) - 09:53, 22 February 2015
• Maximum matching by Edmonds
  Each recursive step returns a cardinality-maximal matching of its input graph. The graph search does not find an augmenting path, nor does it run into a [[Matchings
  4 KB (671 words) - 09:25, 22 February 2015
• All pairs shortest paths
  # A [[Basic graph definitions|directed graph]] <math>G = (V,A)</math> ...e cycle, a shortest path exists, and at least one shortest path is [[Basic graph definitions#Paths|simple]] (because such a path may only contain cycles of
  1 KB (259 words) - 12:56, 22 October 2014
• Repeated depth-first search
  '''Algorithmic problem:''' [[Exhaustive graph traversal]] ...ns#Forests, trees, branchings, arborescences|branching]] that is a [[Basic graph definitions#Subgraphs|spanning subgraph]] of <math>G</math> (cf. [[Depth-fi
  2 KB (294 words) - 07:28, 3 November 2014
• Hopcroft-Tarjan
  [[Category:Graph Algorithms]] ## The '''depth''' of <math>v</math> in the [[Basic graph definitions#Forests, trees, branchings, arborescences|arborescence]] create
  6 KB (1,028 words) - 13:31, 3 November 2015
• Bipartite graph
  [[File:Bipartite-graph.png|200px|thumb|right|A simple bipartite graph]] An undirected graph <math>G=(V,E)</math> is called '''bipartite''' if there is a partition of <
  2 KB (319 words) - 11:33, 13 October 2014
• Alternating paths algorithm
  '''Prerequisites:''' The graph <math>G</math> is [[Bipartite graph|bipartite]].
  1 KB (190 words) - 13:38, 27 January 2015
• Kosaraju
  [[Category:Graph Algorithms]] ...t <math>G^t=(V,A^t)</math> be the [[Basic graph definitions#Transpose of a graph|transpose]] of <math>G=(V,A)</math>.
  4 KB (789 words) - 07:37, 2 November 2015
• Blocking flow by Dinic
  ...nitions#Flow-augmenting paths and saturated arcs|flow-augmenting]] [[Basic graph definitions#Paths|ordinary <math>(s,t)</math>-path]] in <math>G</math>. ...rch|DFS]] from <math>s</math> with two modifications: (1) The search may [[Graph traversal#Remarks|terminate early]], namely when <math>t</math> is seen; (2
  3 KB (479 words) - 08:37, 7 December 2015
• Classical eulerian cycle algorithm
  ## Remove <math>(x,y)</math> from the graph. ...er, the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian.
  4 KB (673 words) - 08:15, 2 November 2015
• Three indians' algorithm
  There is no more [[Basic graph definitions#Paths|ordinary <math>(s,t)</math>-path]] in <math>G</math>. ...4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph|transpose]] of <math>G</math> with the value of <math>T(v_0)</math> as comp
  4 KB (788 words) - 11:27, 16 March 2017
• Classical bipartite cardinality matching
  [[Cardinality-maximal matching|Cardinality-maximal matching]] in [[Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]]. ...ersal|graph traversal strategy]] is to be chosen that generates an [[Basic graph definitions#Forests, trees, branchings, arborescences|arborescence]] rooted
  7 KB (1,284 words) - 08:49, 22 February 2015
• Ford-Fulkerson
  ...dition is fulfilled, and nothing is to show. So consider the case that the graph traversal does hit <math>t</math>. Then an <math>(s,t)</math>-path is found '''Proof:''' A graph search from <math>s</math> requires <math>\Omicron (m)</math> . Obviously,
  3 KB (425 words) - 11:49, 23 June 2015
• Single source single target shortest paths
  # A directed graph <math>G=(V,A)</math>
  416 bytes (69 words) - 10:39, 20 October 2014
• Basic graph definitions
  # A '''directed graph''' <math>G=(V,A)</math> consists of a finite set <math>V</math> of '''nodes # An undirected graph <math>G=(V,E)</math> consists of a finite set <math>V</math> of '''nodes'''
  15 KB (2,712 words) - 14:47, 16 May 2015
• Single source shortest paths
  # A directed graph <math>G=(V,A)</math>
  470 bytes (79 words) - 10:32, 20 October 2014
• Dinic
  # Construct the [[Basic graph definitions#Cycles|acyclic]] [[Basic graph definitions#Subgraphs|subgraph]] <math>G'=(V',A')</math> of the residual ne
  2 KB (334 words) - 10:43, 8 January 2015
• Basic flow definitions
  # [[Basic graph definitions]] ...definitions#Directed and undirected graphs|anti-symmetric, simple directed graph]], unless stated otherwise.
  11 KB (2,126 words) - 13:42, 17 November 2015
• Branching by Edmonds
  ...:''' The output of a recursive call is a maximum branching of the weighted graph that was the input for this recursive call. By definition, a critical graph contains one incoming arc for each node that does have incoming arcs. There
  7 KB (1,243 words) - 07:59, 8 November 2015
• Max-Flow Problems
  # [[Basic graph definitions]] # A directed graph <math>G=(V,A)</math>.
  4 KB (786 words) - 08:58, 31 March 2018
• Basics of shortest paths
  ...a [[Basic graph definitions#Directed and undirected graphs|simple directed graph]] and for each arc <math>a\in A</math> let <math>\ell(a)</math> be a real n ...th''' of an [[Basic graph definitions#Paths|ordinary path]] (incl. [[Basic graph definitions#Cycles|ordinary cycles]]) is the sum of the lengths of all arc
  11 KB (2,059 words) - 14:34, 5 December 2014
• Hungarian method
  ...matching]] in [[Basic graph definitions#Complete graphs|complete]] [[Basic graph definitions#Bipartite and k-partite graphs|bipartite]] graphs <math>G=(V_1\ ...v\}</math> and <math>T:=\emptyset</math> and a dynamically growing [[Basic graph definitions#Forests, trees, branchings, arborescences|arborescence]] <math>
  6 KB (1,033 words) - 17:26, 27 February 2015
• Hopcroft-Karp
  [[Cardinality-maximal matching|Cardinality-maximal matching]] in [[Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]]. ...math>S</math> of [[Breadth-first search|BFS]] runs as iterators (cf. the [[Graph traversal#Remarks|remark on iterators]]). The [[Matchings in graphs#Finding
  6 KB (1,029 words) - 15:00, 6 December 2014
• Breadth-first search
  [[Category:Graph Traversal]] '''Algorithmic problem:''' [[Graph traversal]]
  7 KB (1,165 words) - 07:50, 26 October 2015
• Successive shortest paths
  ...minimal sets|inclusion-maximal]] subpaths of <math>C</math> whose [[Basic graph definitions#Paths|internal nodes]] do not belong to <math>p</math>. In oth # the subpath of the [[Basic graph definitions#Transpose|transpose]] of <math>p</math> from the start node of
  6 KB (1,107 words) - 10:08, 6 May 2015
• Depth-first search
  [[Category:Graph Traversal]] '''Algorithmic problem:''' [[Graph traversal]]
  11 KB (1,966 words) - 06:52, 26 October 2015
• Asymptotic complexity of algorithms
  ...f edges/arcs in a [[Basic graph definitions#Directed and undirected graphs|graph]].
  4 KB (700 words) - 05:54, 25 April 2016
• Preflow-push
  # The current arc of a node is an outgoing arc of the node's in the residual graph. In the list of all of these arcs, no admissible arc precedes the current a For the [[Basic graph definitions#Subgraphs|subgraph induced]] by <math>V\setminus\{s\}</math>, t
  9 KB (1,560 words) - 03:53, 20 June 2017
• Dijkstra
  [[Category:Graph Algorithms]] ...er one from <math>t</math> on the [[Basic graph definitions#Transpose of a graph|transpose]] of <math>G</math>. This variant is called '''bidirectional sear
  10 KB (1,765 words) - 08:35, 14 January 2021
• Kruskal for maximum spanning forest
  #The [[undirected graph]] <math>F_i = (V,E_i)</math>, where <math>E_i</math> is the set of all sele #For the [[undirected graph]] <math>F_i = (V,E_i)</math>, there is a maximum spanning forest <math>F_i'
  5 KB (812 words) - 18:31, 20 September 2015
• Negative cycle-canceling
  ...blems|maximum flow]] from <math>s</math> to <math>t</math> in the extended graph (cost factors and balance values are disregarded). ...arithmetic operations and comparisons of flows are arc-wise. For a [[Basic graph definitions#Cycles|generalized cycle]] <math>C</math> and <math>\varepsilon
  7 KB (1,256 words) - 15:18, 5 February 2015
• Directed Tree
  # A '''directed tree''' is a directed graph <math>T = (V,A)</math> with a designated node <math>r \in V</math>, the ''' ...th>v \in V</math> and let <math>d_v</math> denote <math>v</math>'s [[Basic graph definitions#Adjacency, incidence, and degree|outdegree]]. If <math>d_v > 0<
  7 KB (1,284 words) - 11:29, 26 May 2015
• Binary search tree
  ...es]], "well-formed" means that, for any node, there is exactly one [[Basic graph definitions#Paths|path]] from the root to that node.
  2 KB (353 words) - 06:14, 6 July 2015
• Bellman-Ford
  ...atrix <math>L</math>, where <math>n=|V|</math>. This matrix represents the graph and the arc lengths and will not be changed throughout the algorithm.
  2 KB (393 words) - 22:51, 19 June 2015
• Floyd-Warshall
  ...hoortest <math>(v,w</math>-path subject to the constraint that all [[Basic graph definitions#Paths|internal nodes]] are taken from <math>\{u_1, \ldots, u_n
  3 KB (510 words) - 09:28, 24 May 2022
• Ahuja-Orlin
  A [[Breadth-first search|BFS]] is run on the [[Basic graph definitions#Transpose|transpose]] of <math>G</math> with start node <math>t
  8 KB (1,416 words) - 07:59, 30 November 2015