EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 57 (2023) RAIRO-Theor. Inf. Appl., 57 (2023) 3 References
Open Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 57, 2023
Article Number 3
Number of page(s) 20
DOI https://doi.org/10.1051/ita/2023002
Published online 08 March 2023
  1. B. Bergougnoux and M. Kanté Fast exact algorithms for some connectivity problems parameterized by clique-width. Theor. Comput. Sci. 782 (2019) 30–53. [Google Scholar]
  2. A. Björklund, T. Husfeldt, P. Kaski and M. Koivisto, Fourier meets Möbius: fast subset convolution, in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, Association for Computing Machinery, New York, NY, USA (2007), pp. 67–74. [Google Scholar]
  3. A. Bondy and U. Murty, Graph Theory, Graduate Texts in Mathematics. Springer London (2008). [Google Scholar]
  4. C.J. Colbourn and L.K. Stewart Permutation graphs: connected domination and Steiner trees. Discrete Math. 86 (1990) 179–189. [CrossRef] [MathSciNet] [Google Scholar]
  5. D.G. Corneil, H. Lerchs and S.L. Burlingham Complement reducible graphs. Discrete Appl. Math. 3 (1981) 163–174. [CrossRef] [MathSciNet] [Google Scholar]
  6. D.G. Corneil, Y. Perl and L.K. Stewart, A linear recognition algorithm for cographs. SIAM J. Comput. 14 (1985) 926–934. [Google Scholar]
  7. B. Courcelle, J. Engelfriet and G. Rozenberg Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46 (1993) 218–270. [CrossRef] [Google Scholar]
  8. M. Cygan, M. Pilipczuk, M. Pilipczuk and J.O. Wojtaszczyk Kernelization hardness of connectivity problems in d-degenerate graphs. Discrete Appl. Math. 160 (2012) 2131–2141. [CrossRef] [MathSciNet] [Google Scholar]
  9. A. D’Atri and M. Moscarini Distance-hereditary graphs, Steiner trees, and connected domination. SIAM J. Comput. 17 (1988) 521–538. [Google Scholar]
  10. M.C. Dourado, R.A. Oliveira, F. Protti and U.S. Souza, Conexäo de Terminais com Numero Restrito de Roteadores e Elos, in Proceedings of XLVI Simpósio Brasileiro de Pesquisa Operacional (2014) 2965–2976. [Google Scholar]
  11. M.C. Dourado, R.A. Oliveira, F. Protti and U.S. Souza Design of connection networks with bounded number of non-terminal vertices, in Proceedings of V Latin-American Workshop on Cliques in Graphs. Matematica Contemporânea, vol. 42, SBM, Buenos Aires (2014) 39–47. [Google Scholar]
  12. S.E. Dreyfus and R.A. Wagner The Steiner problem in graphs. Networks 1 (1971) 195–207. [Google Scholar]
  13. M. Farber Characterizations of strongly chordal graphs. Discrete Math. 43 (1983) 173–189. [CrossRef] [MathSciNet] [Google Scholar]
  14. M.R. Fellows, F.A. Rosamond, U. Rotics and S. Szeider Clique-width is NP-complete. SIAM J. Discrete Math. 23 (2009) 909–939. [Google Scholar]
  15. F.V. Fomin, P.A. Golovach, D. Lokshtanov and S. Saurabh, Clique-width: on the price of generality, in Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, SIAM (2009) 825–834. [Google Scholar]
  16. M.R. Garey and D.S. Johnson The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32 (1977) 826–834. [Google Scholar]
  17. L. Gargano, M. Hammar, P. Hell, L. Stacho and U. Vaccaro Spanning spiders and light-splitting switches. Discrete Math. 285 (2004) 83–95. [CrossRef] [MathSciNet] [Google Scholar]
  18. F.K. Hwang, D.S. Richards and P. Winter The Steiner tree problem. Ann. Discrete Math. 53 (1992). [Google Scholar]
  19. A. Itai, C.H. Papadimitriou and J.L. Szwarcfiter Hamilton paths in grid graphs. SIAM J. Comput. 11 (1982) 676–686. [Google Scholar]
  20. R.M. Karp, Reducibility among Combinatorial Problems. Springer US, Boston, MA (1972), pp. 85–103. [Google Scholar]
  21. G. Lin and G. Xue On the terminal Steiner tree problem. Inf. Process. Lett. 84 (2002) 103–107. [CrossRef] [Google Scholar]
  22. G.D. Lozzo and I. Rutter, Strengthening Hardness Results to 3-Connected Planar Graphs. Preprint arXiv:1607.02346 (2016). [Google Scholar]
  23. C.L. Lu, C.Y. Tang and R.C.-T. Lee, The full Steiner tree problem. Theor. Comput. Sci. 306 (2003) 55–67. [Google Scholar]
  24. A.A. Melo, C.M.H. Figueiredo and U.S. Souza, Connecting terminals using at most one router, in Proceedings of VII Latin-American Workshop on Cliques in Graphs. Vol. 45 of Matemática Contemporânea. SBM (2017) 49–57. [Google Scholar]
  25. A.A. Melo, C.M.H. Figueiredo and U.S. Souza, A multivariate analysis of the strict terminal connection problem. J. Comput. Syst. Sci. 111 (2020) 22–41. [CrossRef] [Google Scholar]
  26. A.A. Melo, C.M.H. Figueiredo and U.S. Souza, On the terminal connection problem, in Proceedings of 47th International Conference on Current Trends in Theory and Practice of Computer Science. Vol. 12607 of Lecture Notes in Computer Science. Springer-Verlag New York, Inc. (2021) 278–292. [Google Scholar]
  27. A.A. Melo, C.M.H. Figueiredo and U.S. Souza On undirected two-commodity integral flow, disjoint paths and strict terminal connection problems. Networks 77 (2021) 559–571. [Google Scholar]
  28. H. Muller Hamiltonian circuits in chordal bipartite graphs. Discrete Math. 156 (1996) 291–298. [CrossRef] [MathSciNet] [Google Scholar]
  29. H. Muller and A. Brandstädt The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs. Theor. Comput. Sci. 53 (1987) 257–265. [Google Scholar]
  30. J. Nederlof Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica 65 (2013) 868–884. [CrossRef] [MathSciNet] [Google Scholar]
  31. D. Watel, M.-A. Weisser, C. Bentz and D. Barth, Steiner problems with limited number of branching nodes, in Proceedings of 20th International Colloquium on Structural Information and Communication Complexity. Vol. 8179 of Lecture Notes in Computer Science. Springer-Verlag New York, Inc. (2013) 310–321. [Google Scholar]
  32. D. Watel, M.-A. Weisser, C. Bentz and D. Barth Directed Steiner trees with diffusion costs. J. Combinat. Optim. 32 (2016) 1089–1106. [CrossRef] [Google Scholar]
  33. K. White, M. Farber and W. Pulleyblank Steiner trees, connected domination and strongly chordal graphs. Networks 15 (1985) 109–124. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.