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 146 articles )

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

1 2 3 ... 6 7 8 next

  1. Beisegel, Jesse; Denkert, Carolin; Köhler, Ekkehard; Krnc, Matjaž; Pivač, Nevena; Scheffler, Robert; Strehler, Martin: The recognition problem of graph search trees (2021)
  2. Chaplick, Steven; Fomin, Fedor V.; Golovach, Petr A.; Knop, Dušan; Zeman, Peter: Kernelization of graph Hamiltonicity: proper (H)-graphs (2021)
  3. Da Lozzo, Giordano; Eppstein, David; Goodrich, Michael T.; Gupta, Siddharth: C-planarity testing of embedded clustered graphs with bounded dual carving-width (2021)
  4. Di Battista, Giuseppe; Frati, Fabrizio; Patrignani, Maurizio; Tais, Marco: Schematic representation of large biconnected graphs (2021)
  5. Jansson, Jesper; Mampentzidis, Konstantinos; Rajaby, Ramesh; Sung, Wing-Kin: Computing the rooted triplet distance between phylogenetic networks (2021)
  6. Zhang, Xindi; Li, Bohan; Cai, Shaowei; Wang, Yiyuan: Efficient local search based on dynamic connectivity maintenance for minimum connected dominating set (2021)
  7. Cai, Qingpo; Kang, Jian; Yu, Tianwei: Bayesian network marker selection via the thresholded graph Laplacian Gaussian prior (2020)
  8. Casteigts, Arnaud; Dubois, Swan; Petit, Franck; Robson, John M.: Robustness: a new form of heredity motivated by dynamic networks (2020)
  9. Ducoffe, Guillaume; Marinescu-Ghemeci, Ruxandra; Popa, Alexandru: On the (di)graphs with (directed) proper connection number two (2020)
  10. Fang, Wenjie; Préville-Ratelle, Louis-François: From generalized Tamari intervals to non-separable planar maps (extended abstract) (2020)
  11. Jovanovic, Raka; Voß, Stefan: A matheuristic approach for solving the 2-connected dominating set problem (2020)
  12. Kfoury, Assaf; Sisson, Benjamin: Efficient reassembling of three-regular planar graphs (2020)
  13. Lange, Kenneth: Algorithms from THE BOOK (2020)
  14. Singh, Ranveer: Permanent, determinant, and rank of bi-block graphs (2020)
  15. BezáKová, Ivona; Curticapean, Radu; Dell, Holger; Fomin, Fedor V.: Finding detours is fixed-parameter tractable (2019)
  16. Cardinal, Jean; Doignon, Jean-Paul; Merckx, Keno: Finding a maximum-weight convex set in a chordal graph (2019)
  17. Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes: Compact drawings of 1-planar graphs with right-angle crossings and few bends (2019)
  18. Da Lozzo, Giordano; Rutter, Ignaz: Planarity of streamed graphs (2019)
  19. Dar, Muhammad Abid; Fischer, Andreas; Martinovic, John; Scheithauer, Guntram: An improved flow-based formulation and reduction principles for the minimum connectivity inference problem (2019)
  20. Di Giacomo, Emilio; Liotta, Giuseppe; Patrignani, Maurizio; Rutter, Ignaz; Tappini, Alessandra: NodeTrix planarity testing with small clusters (2019)

1 2 3 ... 6 7 8 next