New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
From MaRDI portal
Publication:2330102
DOI10.1016/j.tcs.2019.06.007zbMath1434.68354arXiv1803.04327OpenAlexW2963116939WikidataQ127567155 ScholiaQ127567155MaRDI QIDQ2330102
Tatiana Romina Hartinger, Nina Chiarelli, V. Leoni, Martin Milanič, Maria Inés Lopez Pujato
Publication date: 18 October 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1803.04327
Analysis of algorithms (68W40) 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) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Algorithm and hardness results on neighborhood total domination in graphs ⋮ Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination ⋮ Total Roman domination for proper interval graphs ⋮ Total 2-domination of proper interval graphs ⋮ A linear algorithm for double Roman domination of proper interval graphs ⋮ A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- (Total) vector domination for graphs with bounded branchwidth
- Graph classes with structured neighborhoods and algorithmic applications
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- On the algorithmic complexity of \(k\)-tuple total domination
- Algorithmic aspects of \(k\)-tuple total domination in graphs
- Finding outer-connected dominating sets in interval graphs
- \(k\)-domination and \(k\)-independence in graphs: A survey
- Minimum 2-tuple dominating set of an interval graph
- \(k\)-tuple total domination in graphs
- Variations of \(Y\)-dominating functions on graphs
- Efficient algorithms for Roman domination on some classes of graphs
- \(k\)-tuple domination in graphs
- A unified approach to domination problems on interval graphs
- Total domination in interval graphs revisited
- Labeling algorithms for domination problems in sun-free chordal graphs
- Independent domination in chordal graphs
- Linear time algorithms on circular-arc graphs
- A new characterization of proper interval graphs
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs
- Improved algorithms for \(k\)-domination and total \(k\)-domination in proper interval graphs
- Subexponential fixed-parameter algorithms for partial vector domination
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- Weighted independent perfect domination on cocomparability graphs
- Power domination in circular-arc graphs
- On the approximability and exact algorithms for vector domination and related problems in graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- The eternal dominating set problem for proper interval graphs
- Optimal greedy algorithms for indifference graphs
- Paired domination on interval and circular-arc graphs
- Bounds on the \(k\)-domination number of a graph
- A linear time algorithm for liar's domination problem in proper interval graphs
- On \(k\)-domination and \(j\)-independence in graphs
- Algorithmic aspects of the \(k\)-domination problem in graphs
- Latency-bounded target set selection in social networks
- The Roberts characterization of proper and unit interval graphs
- Approximating clique-width and branch-width
- Onk-domination and minimum degree in graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- A note on domination in bipartite graphs
- Trees with equal 2-domination and 2-independence numbers
- On the total k-domination number of graphs
- Metric characterizations of proper interval graphs and tree-clique graphs
- Total Domination in Graphs
- On Dominating Sets and Independent Sets of Graphs
- A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
- Dominating sequences under atomic changes with applications in Sierpiński and interval graphs
- The Parameterized Complexity of Domination-Type Problems and Application to Linear Codes
- Total domination in interval graphs
- Total domination in interval graphs
