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

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

1 2 3 4 5 next

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

1 2 3 4 5 next