Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
From MaRDI portal
Publication:4210127
Recommendations
Cited in
(66)- Complexity of maximum cut on interval graphs
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- Linear separation of connected dominating sets in graphs
- On \(H\)-topological intersection graphs
- New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
- The degree-preserving spanning tree problem in strongly chordal and directed path graphs
- Graph classes with structured neighborhoods and algorithmic applications
- Total 2-domination of proper interval graphs
- Dominating sets reconfiguration under token sliding
- The dominating set problem in geometric intersection graphs
- The minimum weakly connected independent set problem: polyhedral results and branch-and-cut
- A survey of selected recent results on total domination in graphs
- On dominating set polyhedra of circular interval graphs
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- scientific article; zbMATH DE number 1522922 (Why is no real title available?)
- Graph classes with structured neighborhoods and algorithmic applications
- Approximability results for the maximum and minimum maximal induced matching problems
- Algorithms for finding clique-transversals of graphs
- Weighted maximum-clique transversal sets of graphs
- On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
- Graphs vertex-partitionable into strong cliques
- Small \(k\)-pyramids and the complexity of determining \(k\)
- Domination problems on \(P_{5}\)-free graphs
- A (2+ε)-Approximation Scheme for Minimum Domination on Circle Graphs
- A linear-time algorithm for paired-domination on circular-arc graphs
- A unified approach to domination problems on interval graphs
- Efficient reduction for path problems on circular-arc graphs
- Efficient algorithms for the conditional covering problem
- Connected domination and dominating clique in trapezoid graphs
- Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs
- Minimum dominating sets of intervals on lines
- Algorithmic aspects of \(b\)-disjunctive domination in graphs
- On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm
- Wireless networking, dominating and packing
- Independent domination in finitely defined classes of graphs
- A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
- On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
- Parameterized complexity of multicut in weighted trees
- Total Domination and Irredundance in Weighted Interval Graphs
- Tuple domination on graphs with the consecutive-zeros property
- Dominating sets and domatic number of circular arc graphs
- Paired domination on interval and circular-arc graphs
- Hamilton cycles in split graphs with large minimum degree
- Efficient and perfect domination on circular-arc graphs
- On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
- Total domination in circular-arc graphs
- On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
- The complexity of dominating set in geometric intersection graphs
- Connected domination
- Total domination in interval graphs
- Total domination in interval graphs
- A linear time algorithm for liar's domination problem in proper interval graphs
- Minimum connected dominating sets of intervals on lines
- Paired-domination problem on distance-hereditary graphs
- Domination in Geometric Intersection Graphs
- Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
- Deferred-query: An efficient approach for some problems on interval graphs
- Independent Domination in Triangle Graphs
- Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals
- Domination cover number of graphs
- On approximation of multiple intruder locating domination number of a graph
- Domination and Cut Problems on Chordal Graphs with Bounded Leafage
- Unique response Roman domination: complexity and algorithms
- An efficient algorithm for distance total domination in block graphs
- scientific article; zbMATH DE number 1445364 (Why is no real title available?)
- A closer look at Hamiltonicity and domination through the lens of diameter and convexity
This page was built for publication: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210127)
