On the terminal connection problem

DOI10.1007/978-3-030-67731-2_20MaRDI QIDQ831820zbMATH OpenOpenAlexFDO

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

Publication date 24 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-67731-2_20

zbMATH Keywords

Steiner treecographsbounded degreestrongly chordal graphsconnection treeterminal vertices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the computational difficulty of the terminal connection problem
• scientific article; zbMATH DE number 6423757
• A multivariate analysis of the strict terminal connection problem
• On the terminal Steiner tree problem.
• Steiner trees, connected domination and strongly chordal graphs

Cites work

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

Cited in

(3)

• On the computational difficulty of the terminal connection problem
• The strict terminal connection problem on chordal bipartite graphs
• Connecting terminals using at most one router

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

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