New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
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
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