Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Electronic Journal of Graph Theory and Applications (EJGTA)
Manuel Streicher
Technische Universitat Kaiserslautern, Germany
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
Simultaneously dominating all spanning trees of a graph Sebastian Johann; Sven O. Krumke; Manuel Streicher
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 10, No 1 (2022): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2022.10.1.5

Abstract

We investigate the problem of simultaneously dominating all spanning trees of a given graph. We prove that on 2-connected graphs, a subset of the vertices dominates all spanning trees of the graph if and only if it is a vertex cover. Using this fact we present an exact algorithm that finds a simultaneous dominating set of minimum size using an oracle for finding a minimum vertex cover. The algorithm can be implemented to run in polynomial time on several graph classes, such as bipartite or chordal graphs. We prove that there is no polynomial time algorithm that finds a minimum simultaneous dominating set on perfect graphs unless P=NP. Finally, we provide a 2-approximation algorithm for finding a minimum simultaneous dominating set.
Co-Authors Sebastian Johann Sven O. Krumke