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

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

1 2 3 4 5 next

  1. Addis, Bernardetta; Aringhieri, Roberto; Grosso, Andrea; Hosteins, Pierre: Hybrid constructive heuristics for the critical node problem (2016)
  2. Brimkov, Boris; Hicks, Illya V.: Chromatic and flow polynomials of generalized vertex join graphs and outerplanar graphs (2016)
  3. Bueno, Lucas Moutinho; Stolfi, Jorge: 3-colored triangulation of 2D maps (2016)
  4. Dittmann, Christoph; Kreutzer, Stephan; Tomescu, Alexandru I.: Graph operations on parity games and polynomial-time algorithms (2016)
  5. Bampas, Evangelos; Bilò, Davide; Drovandi, Guido; Gualà, Luciano; Klasing, Ralf; Proietti, Guido: Network verification via routing table queries (2015)
  6. Bao, Xiaowei; Khajavirad, Aida; Sahinidis, Nikolaos V.; Tawarmalani, Mohit: Global optimization of nonconvex problems with multilinear intermediates (2015)
  7. Bermond, Jean-Claude; Coudert, David; D’Angelo, Gianlorenzo; Moataz, Fatima Zahra: Finding disjoint paths in networks with star shared risk link groups (2015)
  8. Berry, Anne; Brandstädt, Andreas; Giakoumakis, Vassilis; Maffray, Frédéric: Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds (2015)
  9. Bose, Prosenjit; De Carufel, Jean-Lou; Grimm, Carsten; Maheshwari, Anil; Smid, Michiel: Optimal data structures for farthest-point queries in cactus networks (2015)
  10. Chang, Hsien-Chih; Lu, Hsueh-I: A faster algorithm to recognize even-hole-free graphs (2015)
  11. Gamrath, Gerald; Koch, Thorsten; Martin, Alexander; Miltenberger, Matthias; Weninger, Dieter: Progress in presolving for mixed integer programming (2015)
  12. Kim, Eun Jung; Paul, Christophe; Philip, Geevarghese: A single-exponential FPT algorithm for the $K_4$- minor cover problem (2015)
  13. Kosowski, A.; Li, B.; Nisse, N.; Suchan, K.: $k$-chordal graphs: from cops and robber to compact routing via treewidth (2015)
  14. Williamson, Matthew; Subramani, K.: A new algorithm for the minimum spanning tree verification problem (2015)
  15. Andersson, Björn; Raravi, Gurulingesh: Real-time scheduling with resource sharing on heterogeneous multiprocessors (2014)
  16. Babu, Jasine; Basavaraju, Manu; Chandran, L.Sunil; Rajendraprasad, Deepak: 2-connecting outerplanar graphs without blowing up the pathwidth (2014)
  17. Berenbrink, Petra; Krayenhoff, Bruce; Mallmann-Trenn, Frederik: Estimating the number of connected components in sublinear time (2014)
  18. Berry, Anne; Pogorelcnik, Romain; Simonet, Geneviève: Organizing the atoms of the clique separator decomposition into an atom tree (2014)
  19. Caro, S.; Chablat, D.; Goldsztejn, A.; Ishii, D.; Jermann, C.: A branch and prune algorithm for the computation of generalized aspects of parallel robots (2014)
  20. Charbit, Pierre; Habib, Michel; Mamcarz, Antoine: Influence of the tie-break rule on the end-vertex problem (2014)

1 2 3 4 5 next