Domination on Cocomparability Graphs
From MaRDI portal
Publication:3136612
DOI10.1137/0406032zbMath0780.05032OpenAlexW2033410225MaRDI QIDQ3136612
Dieter Kratsch, Lorna K. Stewart
Publication date: 14 October 1993
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0406032
comparability graphdominating setindependent dominating setcocomparability graphtotal dominating setminimum dominating set
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs ⋮ Minimal triangulations of graphs: a survey ⋮ On the independent dominating set polytope ⋮ Dominations in trapezoid graphs ⋮ Computing a dominating pair in an asteroidal triple-free graph in linear time ⋮ Some advances on the set covering polyhedron of circulant matrices ⋮ Parallel algorithms for the domination problems in trapezoid graphs ⋮ One-node cutsets and the dominating set polytope ⋮ Happy set problem on subclasses of co-comparability graphs ⋮ The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs ⋮ Max point-tolerance graphs ⋮ A new LBFS-based algorithm for cocomparability graph recognition ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ On dominating set polyhedra of circular interval graphs ⋮ Weighted independent perfect domination on cocomparability graphs ⋮ Perfect elimination orderings for symmetric matrices ⋮ Proper and unit bitolerance orders and graphs ⋮ Weighted domination of cocomparability graphs ⋮ Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ Complexity of the improper twin edge coloring of graphs ⋮ Efficient algorithms for the minimum connected domination on trapezoid graphs ⋮ Independent set under a change constraint from an initial solution ⋮ Graphs of Linear Clique-Width at Most 3 ⋮ On the kernel and related problems in interval digraphs ⋮ On the intersection of tolerance and cocomparability graphs ⋮ Independent domination in finitely defined classes of graphs ⋮ Cubicity and bandwidth ⋮ Diametral path graphs ⋮ Asteroidal triple-free graphs ⋮ On linear and circular structure of (claw, net)-free graphs ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ A new graph parameter to measure linearity ⋮ Graphs vertex-partitionable into strong cliques ⋮ Connected domination and dominating clique in trapezoid graphs ⋮ Domination and total domination on asteroidal triple-free graphs ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ On total \(f\)-domination: polyhedral and algorithmic results ⋮ Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs ⋮ A linear time algorithm to compute a dominating path in an AT-free graph ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ Linear time algorithms for dominating pairs in asteroidal triple-free graphs ⋮ Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm ⋮ Non-edge orientation and vertex ordering characterizations of some classes of bigraphs ⋮ Small \(k\)-pyramids and the complexity of determining \(k\) ⋮ The complexity of domination problems in circle graphs ⋮ On end-vertices of lexicographic breadth first searches ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs ⋮ Happy set problem on subclasses of co-comparability graphs ⋮ Improved bottleneck domination algorithms ⋮ On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs ⋮ Graphs of linear clique-width at most 3 ⋮ Hardness and approximation of minimum distortion embeddings ⋮ A survey of selected recent results on total domination in graphs ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ The hub number of co-comparability graphs ⋮ A vertex ordering characterization of simple-triangle graphs ⋮ Connected Domination ⋮ New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ Algorithms on Subtree Filament Graphs ⋮ On the Cubicity of AT-Free Graphs and Circular-Arc Graphs ⋮ Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ Coloring squares of graphs via vertex orderings ⋮ Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ Fast Diameter Computation within Split Graphs
