Algorithm 447

Algorithm 447: effcient algorithms for graph manipulation. Efficient algorithms are presented for partitioning a graph into connected components, biconnected components and simple paths. The algorithm for partitioning of a graph into simple paths of iterative and each iteration produces a new path between two vertices already on paths. (The start vertex can be specified dynamically.) If V is the number of vertices and E is the number of edges, each algorithm requires time and space proportional to max (V, E) when executed on a random access computer,

This software is also peer reviewed by journal TOMS.

References in zbMATH (referenced in 139 articles )

Showing results 1 to 20 of 139.
Sorted by year (citations)

1 2 3 ... 5 6 7 next

  1. Chaplick, Steven; Fomin, Fedor V.; Golovach, Petr A.; Knop, Dušan; Zeman, Peter: Kernelization of graph Hamiltonicity: proper (H)-graphs (2021)
  2. Cai, Qingpo; Kang, Jian; Yu, Tianwei: Bayesian network marker selection via the thresholded graph Laplacian Gaussian prior (2020)
  3. Casteigts, Arnaud; Dubois, Swan; Petit, Franck; Robson, John M.: Robustness: a new form of heredity motivated by dynamic networks (2020)
  4. Ducoffe, Guillaume; Marinescu-Ghemeci, Ruxandra; Popa, Alexandru: On the (di)graphs with (directed) proper connection number two (2020)
  5. Fang, Wenjie; Préville-Ratelle, Louis-François: From generalized Tamari intervals to non-separable planar maps (extended abstract) (2020)
  6. Jovanovic, Raka; Voß, Stefan: A matheuristic approach for solving the 2-connected dominating set problem (2020)
  7. Kfoury, Assaf; Sisson, Benjamin: Efficient reassembling of three-regular planar graphs (2020)
  8. Lange, Kenneth: Algorithms from THE BOOK (2020)
  9. Singh, Ranveer: Permanent, determinant, and rank of bi-block graphs (2020)
  10. BezáKová, Ivona; Curticapean, Radu; Dell, Holger; Fomin, Fedor V.: Finding detours is fixed-parameter tractable (2019)
  11. Cardinal, Jean; Doignon, Jean-Paul; Merckx, Keno: Finding a maximum-weight convex set in a chordal graph (2019)
  12. Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes: Compact drawings of 1-planar graphs with right-angle crossings and few bends (2019)
  13. Da Lozzo, Giordano; Rutter, Ignaz: Planarity of streamed graphs (2019)
  14. Dar, Muhammad Abid; Fischer, Andreas; Martinovic, John; Scheithauer, Guntram: An improved flow-based formulation and reduction principles for the minimum connectivity inference problem (2019)
  15. Di Giacomo, Emilio; Liotta, Giuseppe; Patrignani, Maurizio; Rutter, Ignaz; Tappini, Alessandra: NodeTrix planarity testing with small clusters (2019)
  16. Dimitrios Michail, Joris Kinable, Barak Naveh, John V Sichi: JGraphT - A Java library for graph data structures and algorithms (2019) arXiv
  17. Ducoffe, Guillaume: Finding cut-vertices in the square roots of a graph (2019)
  18. East, James; Gadouleau, Maximilien; Mitchell, James D.: Structural aspects of semigroups based on digraphs (2019)
  19. Fomin, Fedor V.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav: Finding, hitting and packing cycles in subexponential time on unit disk graphs (2019)
  20. Kashyop, Manas Jyoti; Nagayama, Tsunehiko; Sadakane, Kunihiko: Faster algorithms for shortest path and network flow based on graph decomposition (2019)

1 2 3 ... 5 6 7 next