On the computational difficulty of the terminal connection problem

DOI10.1051/ITA/2023002zbMATH Open1511.68201OpenAlexW4323647901MaRDI QIDQ6041044FDOQ6041044

Authors: Alexsander A. de Melo, Celina M. H. de Figueiredo, Uéverton S. Souza 

Publication date: 25 May 2023

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ita/2023002

Recommendations

• On the terminal connection problem
• A multivariate analysis of the strict terminal connection problem
• scientific article; zbMATH DE number 6423757
• Complexity of Steiner tree in split graphs -- dichotomy results
• The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy

zbMATH Keywords

parameterized complexitySteiner treecographscomputational difficulty of problemssplit graphsbounded degreestrongly chordal graphsconnection treeterminal vertices

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Graph theory
• Reducibility among combinatorial problems
• Complement reducible graphs
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Handle-rewriting hypergraph grammars
• Clique-width is NP-complete
• Hamilton Paths in Grid Graphs
• The Steiner tree problem
• Characterizations of strongly chordal graphs
• HAMILTONian circuits in chordal bipartite graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A Linear Recognition Algorithm for Cographs
• Fourier meets M\"{o}bius: fast subset convolution
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Steiner trees, connected domination and strongly chordal graphs
• Steiner problems with limited number of branching nodes
• Directed Steiner trees with diffusion costs
• The steiner problem in graphs
• On the terminal Steiner tree problem.
• Clique-width: on the price of generality
• The full Steiner tree problem
• Spanning spiders and light-splitting switches
• Permutation graphs: Connected domination and Steiner trees
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• A multivariate analysis of the strict terminal connection problem
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• On the terminal connection problem

Cited In (8)

• An \(s\)-\(t\) connection problem with adaptability
• On the terminal connection problem
• Complexity of Steiner tree in split graphs -- dichotomy results
• A multivariate analysis of the strict terminal connection problem
• Connecting terminals using at most one router
• The strict terminal connection problem on chordal bipartite graphs
• The One-Terminal TELPAK Problem
• On convexity in split graphs: complexity of Steiner tree and domination

This page was built for publication: On the computational difficulty of the terminal connection problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041044)