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

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

1 2 3 4 5 next

  1. Fang, Wenjie; Préville-Ratelle, Louis-François: The enumeration of generalized Tamari intervals (2017)
  2. Francesco Furiani, Giulio Martella, Alberto Paoluzzi: Geometric Computing with Chain Complexes: Design and Features of a Julia Package (2017) arXiv
  3. Glebov, Roman; Naves, Humberto; Sudakov, Benny: The threshold probability for long cycles (2017)
  4. Horváth, Gábor; Nehaniv, Chrystopher L.; Podoski, Károly: The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs (2017)
  5. Ihm, Insung; Park, Jung-Heum: A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph (2017)
  6. Jansen, Bart M.P.: Turing kernelization for finding long paths and cycles in restricted graph classes (2017)
  7. Jovanovic, Raka; Nishi, Tatsushi; Voß, Stefan: A heuristic approach for dividing graphs into bi-connected components with a size constraint (2017)
  8. Lèbre, Sophie; Gascuel, Olivier: The combinatorics of overlapping genes (2017)
  9. Lenstra, H.W.jun.; Silverberg, A.: Roots of unity in orders (2017)
  10. Lokshtanov, Daniel; Misra, Pranabendu; Ramanujan, M.S.; Saurabh, Saket: Hitting selected (odd) cycles (2017)
  11. Addis, Bernardetta; Aringhieri, Roberto; Grosso, Andrea; Hosteins, Pierre: Hybrid constructive heuristics for the critical node problem (2016)
  12. Bonnet, Édouard; Brettell, Nick; Kwon, O-joung; Marx, Dániel: Parameterized vertex deletion problems for hereditary graph classes with a block property (2016)
  13. Brimkov, Boris; Hicks, Illya V.: Chromatic and flow polynomials of generalized vertex join graphs and outerplanar graphs (2016)
  14. Bueno, Lucas Moutinho; Stolfi, Jorge: 3-colored triangulation of 2D maps (2016)
  15. Damaschke, Peter: Computing giant graph diameters (2016)
  16. Dittmann, Christoph; Kreutzer, Stephan; Tomescu, Alexandru I.: Graph operations on parity games and polynomial-time algorithms (2016)
  17. Bampas, Evangelos; Bilò, Davide; Drovandi, Guido; Gualà, Luciano; Klasing, Ralf; Proietti, Guido: Network verification via routing table queries (2015)
  18. Bao, Xiaowei; Khajavirad, Aida; Sahinidis, Nikolaos V.; Tawarmalani, Mohit: Global optimization of nonconvex problems with multilinear intermediates (2015)
  19. Bermond, Jean-Claude; Coudert, David; D’Angelo, Gianlorenzo; Moataz, Fatima Zahra: Finding disjoint paths in networks with star shared risk link groups (2015)
  20. Berry, Anne; Brandstädt, Andreas; Giakoumakis, Vassilis; Maffray, Frédéric: Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds (2015)

1 2 3 4 5 next