A general framework for path convexities
From MaRDI portal
Publication:2156285
DOI10.1007/s10878-020-00618-9zbMath1495.90164arXiv1702.06112OpenAlexW2592241569MaRDI QIDQ2156285
João Vinicius C. Thompson, Mitre C. Dourado, Raquel S. F. Bravo, Loana Tito Nogueira, Fábio Protti, Uéverton S. Souza
Publication date: 18 July 2022
Published in: Journal of Combinatorial Optimization, Algorithmic Aspects in Information and Management (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.06112
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Paths and cycles (05C38)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity aspects of the triangle path convexity
- The pre-hull number and lexicographic product
- An upper bound on the \(P_3\)-Radon number
- Complexity properties of complementary prisms
- Irreversible conversion of graphs
- Peakless functions on graphs
- Monadic second-order evaluations on tree-decomposable graphs
- Chordless paths through three vertices
- Complexity analysis of \(P_3\)-convexity problems on bounded-degree and planar graphs
- Complexity results related to monophonic convexity
- Triangle path transit functions, betweenness and pseudo-modular graphs
- On the number of connected convex subgraphs of a connected acyclic digraph
- On the computation of the hull number of a graph
- Convex sets in a graph
- On local convexity in graphs
- Convex sets in graphs. II: Minimal path convexity
- Convexity in graphs
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- All structured programs have small tree width and good register allocation
- A partial k-arboretum of graphs with bounded treewidth
- On triangle path convexity in graphs
- The geodetic number of a graph
- Some remarks on the convexity number of a graph
- And/or-convexity: a graph convexity based on processes and deadlock models
- On the hardness of finding the geodetic number of a subcubic graph
- Convexities related to path properties on graphs
- Induced path transit function, monotone and Peano axioms
- Linear time solvable optimization problems on graphs of bounded clique-width
- \(P_3\)-hull number of graphs with diameter two
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The All-Paths Transit Function of a Graph
- On the Convexity of Paths of Length Two in Undirected Graphs
- Geodesic Convexity in Graphs
- Minimal trees and monophonic convexity
- Easy problems for tree-decomposable graphs
- Steiner Trees and Convex Geometries
- Convexity in Graphs and Hypergraphs
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Graph Classes: A Survey
- Convexity and HHD-Free Graphs
- A characterization of the interval function of a connected graph
- Computational Complexity of Geodetic Set
- Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs
