On the computational difficulty of the terminal connection problem

DOI10.1051/ITA/2023002MaRDI QIDQ6041044zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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

Cites work

• A Linear Recognition Algorithm for Cographs
• A multivariate analysis of the strict terminal connection problem
• Characterizations of strongly chordal graphs
• Clique-width is NP-complete
• Clique-width: on the price of generality
• 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
• Handle-rewriting hypergraph grammars
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• On the terminal Steiner tree problem.
• On the terminal connection 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

(8)

• On the terminal connection problem
• The strict terminal connection problem on chordal bipartite graphs
• Connecting terminals using at most one router
• A multivariate analysis of the strict terminal connection problem
• Complexity of Steiner tree in split graphs -- dichotomy results
• An \(s\)-\(t\) connection problem with adaptability
• 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)