Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs
From MaRDI portal
Publication:5890507
DOI10.1137/15M1013389zbMath1331.05209OpenAlexW191877893MaRDI QIDQ5890507
Mamadou Moustapha Kanté, Lhouari Nourine
Publication date: 4 March 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/15m1013389
Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Other problems of combinatorial convexity (52A37) Graph theory (05C99)
Related Items
A polynomial time algorithm for geodetic hull number for complementary prisms ⋮ Extended dualization: application to maximal pattern mining ⋮ Two classes of graphs in which some problems related to convexity are efficiently solvable ⋮ Computing the hull number in toll convexity ⋮ The geodetic hull number is hard for chordal graphs ⋮ Algorithms and complexity for geodetic sets on partial grids ⋮ The Geodetic Hull Number is Hard for Chordal Graphs ⋮ Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs
Cites Work
- Graphs with few \(P_4\)'s under the convexity of paths of order three
- On the geodetic and the hull numbers in strong product graphs
- On rigid circuit graphs
- Some remarks on the geodetic number of a graph
- The multiple facets of the canonical direct unit implicational basis
- Complexity results related to monophonic convexity
- On the computation of the hull number of a graph
- The theory of convex geometries
- The hull number of a graph
- Distance-hereditary graphs
- Candidate keys for relations
- On triangle path convexity in graphs
- The hull number of an oriented graph
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- On the Steiner, geodetic and hull numbers of graphs
- On the hull number of some graph classes
- Linear time solvable optimization problems on graphs of bounded clique-width
- Incidence matrices and interval graphs
- Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers
- Geodesic Convexity in Graphs
- Computing Minimum Geodetic Sets of Proper Interval Graphs
- On the Hull Number of Triangle-Free Graphs
- Enumeration of the Monomials of a Polynomial and Related Complexity Classes
- Convexity in Graphs and Hypergraphs
- Convexity and HHD-Free Graphs
- An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Finding Branch-Decompositions and Rank-Decompositions
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
