The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments

DOI10.1007/978-3-319-59605-1_3zbMath1494.68189OpenAlexW2617667333MaRDI QIDQ4632200

Venkatesh Raman, Arindam Biswas, Srinivasa Rao Satti, Varunkumar Jayapaul

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-59605-1_3

zbMATH Keywords

tournamentdominating setkingd-cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

New Results on Directed Edge Dominating Set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterizing above or below guaranteed values
• On finding a minimum dominating set in a tournament
• On the bounded domination number of tournaments
• On limited nondeterminism and the complexity of the V-C dimension
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Sorting and Selection with Imprecise Comparisons
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Finding Scores in Tournaments
• Searching for Sorted Sequences of Kings in Tournaments
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
• Faster Parameterized Algorithms Using Linear Programming
• Polynomial Fixed-parameter Algorithms: A Case Study for Longest Path on Interval Graphs
• A Constructive Solution to a Tournament Problem

This page was built for publication: The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments