Characterizing and computing in linear time mutual-visibility parameters in distance-hereditary graphs
computational complexitydistance-hereditary graphsgraph algorithmsgraph classesmutual-visibilitysplit decomposition
Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
The mutual-visibility problem in a graph \(G\) asks for the cardinality of a largest set of vertices \(X \subseteq V (G)\) so that for any two vertices \(x, y \in X\) there is a shortest \(x, y\)-path whose internal vertices are all not in \(X\). Based on the extension of the visibility property of vertices that are in and/or outside \(X\), variations of this problem exist. It is known that solving the mutual-visibility problem in all its variations is NP-complete. In contrast, exact formulas have been shown for special graph classes like paths, cycles, blocks, cographs, and for the Cartesian product of some simple graphs like paths, cliques, and cycles. In this paper, the authors study the (variations of) mutual-visibility problem in the context of distance-hereditary graphs. In particular, they introduce the direct canonical decomposition of a graph as a tool for defining useful structural properties of the graphs studied, and then show that such properties allow one to devise a linear-time algorithm for solving all the variants of the mutual-visibility problem for distance-hereditary graphs. Finally, the authors prove that a recently posed conjecture about the total mutual-visibility number of distance-hereditary graphs holds.
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- A Combinatorial Decomposition Theory
- A general position problem in graph theory
- Arbitrary pattern formation on infinite regular tessellation graphs
- Complement reducible graphs
- Distance-hereditary graphs
- Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
- Fast Uniform Scattering on a Grid for Asynchronous Oblivious Robots
- General position sets in two families of Cartesian product graphs
- Graph classes between parity and distance-hereditary graphs
- Graph Classes: A Survey
- Graphs with total mutual-visibility number zero and total mutual-visibility in Cartesian products
- scientific article; zbMATH DE number 3290993 (Why is no real title available?)
- Lower (total) mutual-visibility number in graphs
- Mutual and total mutual visibility in hypercube-like graphs
- Mutual visibility in graphs
- Mutual-visibility and general position in double graphs and in Mycielskians
- Mutual-visibility in distance-hereditary graphs: a linear-time algorithm
- Mutual-visibility in strong products of graphs via total mutual-visibility
- Mutual-visibility problems on graphs of diameter two
- Mutual-visibility sets in Cartesian products of paths and cycles
- On general position sets in Cartesian products
- On the general position number of two classes of graphs
- On the general position problem on Kneser graphs
- On the mutual visibility in Cartesian products and triangle-free graphs
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- The general position achievement game played on graphs
- The general position number of Cartesian products involving a factor with small diameter
- The monadic second-order logic of graphs XVI : Canonical graph decompositions
- Total mutual-visibility in graphs with emphasis on lexicographic and Cartesian products
- Total mutual-visibility in Hamming graphs
- Transforming trees by successive local complementations
- Uniform scattering of autonomous mobile robots in a grid
- Variety of mutual-visibility problems in graphs
This page was built for publication: Characterizing and computing in linear time mutual-visibility parameters in distance-hereditary graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6930324)
