Domination on Cocomparability Graphs
From MaRDI portal
Publication:3136612
DOI10.1137/0406032zbMATH Open0780.05032OpenAlexW2033410225MaRDI QIDQ3136612FDOQ3136612
Authors: Dieter Kratsch, Lorna 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
Recommendations
dominating settotal dominating setcomparability graphindependent dominating setminimum dominating setcocomparability graph
Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (72)
- The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs
- Graphs with at most two moplexes
- Small \(k\)-pyramids and the complexity of determining \(k\)
- Independent set under a change constraint from an initial solution
- On the kernel and related problems in interval digraphs
- Diametral path graphs
- Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
- Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications
- Happy set problem on subclasses of co-comparability graphs
- Complexity of the improper twin edge coloring of graphs
- On the cubicity of AT-free graphs and circular-arc graphs
- Hardness and approximation of minimum distortion embeddings
- A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
- On end-vertices of lexicographic breadth first searches
- Algorithms on Subtree Filament Graphs
- Efficient algorithms for the minimum connected domination on trapezoid graphs
- Linear time algorithms for dominating pairs in asteroidal triple-free graphs
- Graphs of linear clique-width at most 3
- The complexity of domination problems in circle graphs
- A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
- On the power of graph searching for cocomparability graphs
- On the intersection of tolerance and cocomparability graphs
- Weighted domination of cocomparability graphs
- A survey of selected recent results on total domination in graphs
- Connected Domination
- Fast Diameter Computation within Split Graphs
- On total \(f\)-domination: polyhedral and algorithmic results
- Bibliography on domination in graphs and some basic definitions of domination parameters
- Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
- Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs
- Minimal triangulations of graphs: a survey
- Perfect elimination orderings for symmetric matrices
- Weighted domination on cocomparability graphs
- Cubicity and bandwidth
- On linear and circular structure of (claw, net)-free graphs
- The hub number of co-comparability graphs
- New geometric representations and domination problems on tolerance and multitolerance graphs
- On the independent dominating set polytope
- Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
- Asteroidal triple-free graphs
- Happy set problem on subclasses of co-comparability graphs
- Dominations in trapezoid graphs
- Parallel algorithms for the domination problems in trapezoid graphs
- Independent domination in finitely defined classes of graphs
- Improved bottleneck domination algorithms
- On dominating set polyhedra of circular interval graphs
- Proper and unit bitolerance orders and graphs
- Induced subgraph isomorphism on proper interval and bipartite permutation graphs
- A new LBFS-based algorithm for cocomparability graph recognition
- Max point-tolerance graphs
- Domination and total domination on asteroidal triple-free graphs
- A vertex ordering characterization of simple-triangle graphs
- Graphs vertex-partitionable into strong cliques
- Connected domination and dominating clique in trapezoid graphs
- Maximum induced matching algorithms via vertex ordering characterizations
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs
- Weighted independent perfect domination on cocomparability graphs
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- One-node cutsets and the dominating set polytope
- Graphs of Linear Clique-Width at Most 3
- Coloring squares of graphs via vertex orderings
- Some advances on the set covering polyhedron of circulant matrices
- Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets
- Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number
- Computing a dominating pair in an asteroidal triple-free graph in linear time
- A new graph parameter to measure linearity
- Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs
- Graph Classes and Forbidden Patterns on Three Vertices
- A linear time algorithm to compute a dominating path in an AT-free graph
This page was built for publication: Domination on Cocomparability Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3136612)
