A unified approach to domination problems on interval graphs

DOI10.1016/0020-0190(88)90091-9zbMath0658.05040OpenAlexW2021568739MaRDI QIDQ1111566

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90091-9

zbMATH Keywords

dominating set interval graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

Computing the average distance of an interval graph, On the independent dominating set polytope, Tree-decompositions with bags of small diameter, Solving the maximum internal spanning tree problem on interval graphs in polynomial time, \(\ell ^2_2\) spreading metrics for vertex ordering problems, The Longest Path Problem Is Polynomial on Interval Graphs, The stable set problem and the thinness of a graph, THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS, Max point-tolerance graphs, A new LBFS-based algorithm for cocomparability graph recognition, Restrictions of minimum spanner problems, Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs, Weighted independent perfect domination on cocomparability graphs, On minimum intersection of two minimum dominating sets of interval graphs, Recognizing graphs without asteroidal triples, The \(k\)-hop connected dominating set problem: approximation and hardness, Algorithms for interval structures with applications, On the thinness and proper thinness of a graph, Chronological rectangle digraphs which are two-terminal series-parallel, Unique response Roman domination: complexity and algorithms, Power domination in circular-arc graphs, Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph, The longest path problem has a polynomial solution on interval graphs, Linear algorithm for optimal path cover problem on interval graphs, The 1-fixed-endpoint path cover problem is Polynomial on interval graphs, Interval numbers of powers of block graphs, New sequential and parallel algorithms for interval graph recognition, On coloring problems with local constraints, Dominating sets in perfect graphs, Algorithmic aspects of clique-transversal and clique-independent sets, Parallel algorithms on interval graphs, A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs, Minimum 2-tuple dominating set of an interval graph, On finding the minimum bandwidth of interval graphs, The Roberts characterization of proper and unit interval graphs, Tree 3-spanners on interval, permutation and regular bipartite graphs, Solving problems on generalized convex graphs via mim-width, Minimum dominating sets of intervals on lines, Incorporating negative-weight vertices in certain vertex-search graph algorithms, Generalized vertex covering in interval graphs, An optimal parallel algorithm to construct a tree 3-spanner on interval graphs, Shiftable intervals, Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph, Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs, Fast algorithms for identifying maximal common connected sets of interval graphs, Dominating set of rectangles intersecting a straight line, The \(k\)-power domination problem in weighted trees, Linear algorithm for domatic number problem on interval graphs, An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph, An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs, The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes, New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs, Graph Classes and Forbidden Patterns on Three Vertices, A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs, Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs, Bibliography on domination in graphs and some basic definitions of domination parameters, Algorithm and hardness results in double Roman domination of graphs

Cites Work