On the computational difficulty of the terminal connection problem
DOI10.1051/ita/2023002zbMath1511.68201OpenAlexW4323647901MaRDI QIDQ6041044
Alexsander A. de Melo, Uéverton S. Souza, Celina M. Herrera de Figueiredo
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
cographssplit graphsSteiner treeparameterized complexitycomputational difficulty of problemsstrongly chordal graphsbounded degreeconnection treeterminal vertices
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Directed Steiner trees with diffusion costs
- The full Steiner tree problem
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- On the terminal connection problem
- Characterizations of strongly chordal graphs
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- Complement reducible graphs
- Permutation graphs: Connected domination and Steiner trees
- The Steiner tree problem
- On the terminal Steiner tree problem.
- Spanning spiders and light-splitting switches
- HAMILTONian circuits in chordal bipartite graphs
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- A multivariate analysis of the strict terminal connection problem
- Handle-rewriting hypergraph grammars
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Steiner Problems with Limited Number of Branching Nodes
- Fourier meets M\"{o}bius: fast subset convolution
- Clique-Width is NP-Complete
- A Linear Recognition Algorithm for Cographs
- Steiner trees, connected domination and strongly chordal graphs
- Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Hamilton Paths in Grid Graphs
- Reducibility among Combinatorial Problems
- The steiner problem in graphs
This page was built for publication: On the computational difficulty of the terminal connection problem
