A general framework for path convexities

DOI10.1007/978-3-030-27195-4_25zbMATH Open1495.90164arXiv1702.06112OpenAlexW2592241569MaRDI QIDQ2156285FDOQ2156285

Authors: João Vinicius C. Thompson, Loana T. Nogueira, Fábio Protti, Raquel S. F. Bravo, Mitre C. Dourado, 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)

Abstract: In this work we deal with the so-called path convexities, defined over special collections of paths. For example, the collection of the shortest paths in a graph is associated with the well-known geodesic convexity, while the collection of the induced paths is associated with the monophonic convexity; and there are many other examples. Besides reviewing the path convexities in the literature, we propose a general path convexity framework, of which most existing path convexities can be viewed as particular cases. Some benefits of the proposed framework are the systematization of the algorithmic study of related problems and the possibility of defining new convexities not yet investigated.

Full work available at URL: https://arxiv.org/abs/1702.06112

Recommendations

• All-path convexity: combinatorial and complexity aspects.
• Convexities related to path properties on graphs
• On finite convexity spaces induced by sets of paths in graphs
• Convex sets in graphs. II: Minimal path convexity
• Convex geometries over induced paths with bounded length

zbMATH Keywords

graph convexityalgorithmic complexitypath convexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Paths and cycles (05C38)

Cites Work

• Graph Classes: A Survey
• On local convexity in graphs
• A partial k-arboretum of graphs with bounded treewidth
• Linear time solvable optimization problems on graphs of bounded clique-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graph structure and monadic second-order logic. A language-theoretic approach
• Title not available (Why is that?)
• Easy problems for tree-decomposable graphs
• Convexity in Graphs and Hypergraphs
• Title not available (Why is that?)
• Triangle path transit functions, betweenness and pseudo-modular graphs
• On the computation of the hull number of a graph
• Convex sets in graphs. II: Minimal path convexity
• On triangle path convexity in graphs
• Convexities related to path properties on graphs
• Complexity aspects of the triangle path convexity
• Geodesic Convexity in Graphs
• An upper bound on the \(P_3\)-Radon number
• Convex partitions of graphs induced by paths of order three
• Irreversible conversion of graphs
• Complexity results related to monophonic convexity
• Minimal trees and monophonic convexity
• Steiner trees and convex geometries
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Convexity and HHD-Free Graphs
• The pre-hull number and lexicographic product
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• The geodetic number of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Monadic second-order evaluations on tree-decomposable graphs
• The All-Paths Transit Function of a Graph
• The longest path transit function of a graph and betweenness
• A characterization of the interval function of a connected graph
• Chordless paths through three vertices
• Convexity in graphs
• Convex sets in a graph
• All structured programs have small tree width and good register allocation
• On the convexity of paths of length two in undirected graphs
• Complexity properties of complementary prisms
• Complexity analysis of \(P_3\)-convexity problems on bounded-degree and planar graphs
• Induced path transit function, monotone and Peano axioms
• Peakless functions on graphs
• Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs
• Computational Complexity of Geodetic Set
• Some remarks on the convexity number of a graph
• On the number of connected convex subgraphs of a connected acyclic digraph
• And/or-convexity: a graph convexity based on processes and deadlock models
• \(P_3\)-hull number of graphs with diameter two
• On the hardness of finding the geodetic number of a subcubic graph
• Two-path convexity in clone-free regular multipartite tournaments

Cited In (4)

• On finite convexity spaces induced by sets of paths in graphs
• ECO method and hill-free generalized Motzkin paths
• Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs
• Convexities related to path properties on graphs

This page was built for publication: A general framework for path convexities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2156285)