Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
From MaRDI portal
Publication:4210127
DOI10.1137/S0097539792238431zbMATH Open0911.05051MaRDI QIDQ4210127FDOQ4210127
Authors: Maw-Shang Chang 
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10)
Cited In (65)
- Graph classes with structured neighborhoods and algorithmic applications
- On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm
- A linear time algorithm for liar's domination problem in proper interval graphs
- Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
- Weighted maximum-clique transversal sets of graphs
- Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs
- Hamilton cycles in split graphs with large minimum degree
- Minimum connected dominating sets of intervals on lines
- Complexity of maximum cut on interval graphs
- Linear separation of connected dominating sets in graphs
- Parameterized complexity of multicut in weighted trees
- A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
- The complexity of dominating set in geometric intersection graphs
- Total domination in circular-arc graphs
- Paired-domination problem on distance-hereditary graphs
- Minimal dominating sets in graph classes: combinatorial bounds and enumeration
- On \(H\)-topological intersection graphs
- A survey of selected recent results on total domination in graphs
- On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
- Connected Domination
- The degree-preserving spanning tree problem in strongly chordal and directed path graphs
- Tuple domination on graphs with the consecutive-zeros property
- The minimum weakly connected independent set problem: polyhedral results and branch-and-cut
- Algorithmic aspects of \(b\)-disjunctive domination in graphs
- Independent Domination in Triangle Graphs
- Deferred-query: An efficient approach for some problems on interval graphs
- Title not available (Why is that?)
- Graph classes with structured neighborhoods and algorithmic applications
- Small \(k\)-pyramids and the complexity of determining \(k\)
- A (2+ε)-Approximation Scheme for Minimum Domination on Circle Graphs
- Paired domination on interval and circular-arc graphs
- Dominating sets reconfiguration under token sliding
- A linear-time algorithm for paired-domination on circular-arc graphs
- Independent domination in finitely defined classes of graphs
- Efficient and perfect domination on circular-arc graphs
- Total 2-domination of proper interval graphs
- On dominating set polyhedra of circular interval graphs
- Dominating sets and domatic number of circular arc graphs
- An efficient algorithm for distance total domination in block graphs
- Domination in Geometric Intersection Graphs
- Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals
- Efficient algorithms for the conditional covering problem
- Domination problems on P5-free graphs
- On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators
- Graphs vertex-partitionable into strong cliques
- Connected domination and dominating clique in trapezoid graphs
- Total Domination and Irredundance in Weighted Interval Graphs
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- Approximability results for the maximum and minimum maximal induced matching problems
- Algorithms for finding clique-transversals of graphs
- Wireless networking, dominating and packing
- On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
- On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
- Total domination in interval graphs
- Total domination in interval graphs
- The Dominating Set Problem in Geometric Intersection Graphs
- A unified approach to domination problems on interval graphs
- Efficient reduction for path problems on circular-arc graphs
- New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
- Domination cover number of graphs
- A closer look at Hamiltonicity and domination through the lens of diameter and convexity
- Unique response Roman domination: complexity and algorithms
- Domination and Cut Problems on Chordal Graphs with Bounded Leafage
- Title not available (Why is that?)
- On approximation of multiple intruder locating domination number of a graph
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)
