Computing the hull number in toll convexity

A tolled walk W between vertices u and v in a graph G is a walk in which u is adjacent only to the second vertex of W and v is adjacent only to the second-to-last vertex of W . A set S ⊆ V ( G ) is toll convex if the vertices contained in any tolled walk between two vertices of S are contained in S...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2022-08, Vol.315 (1), p.121-140
Main Author: Dourado, Mitre C.
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Apexes
Business and Management
Combinatorics
Computational geometry
Convexity
Graph theory
Graphs
Operations research
Operations Research/Decision Theory
Original Research
Polynomials
Theory of Computation
Tolls
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A tolled walk W between vertices u and v in a graph G is a walk in which u is adjacent only to the second vertex of W and v is adjacent only to the second-to-last vertex of W . A set S ⊆ V ( G ) is toll convex if the vertices contained in any tolled walk between two vertices of S are contained in S . The toll convex hull of S is the minimum toll convex set containing  S . The toll hull number of G is the minimum cardinality of a set whose toll convex hull is V ( G ). The main contribution of this work is a polynomial-time algorithm for computing the toll hull number of a general graph.
ISSN:0254-5330
1572-9338
DOI:10.1007/s10479-022-04694-4