Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00488
Finding a MaximumWeight Convex Set in a Chordal Graph
Vol. 23, no. 2, pp. 167190, 2019. Regular paper.
Abstract We consider a natural combinatorial optimization problem on chordal graphs, the class of graphs with no induced cycle of length four or more.
A subset of vertices of a chordal graph is (monophonically) convex if it contains the vertices of all
chordless paths between any two vertices of the set. The problem is to find a maximumweight convex subset
of a given vertexweighted chordal graph. It generalizes previously studied special cases in trees
and split graphs. It also happens to be closely related to the closure problem in partially ordered sets and directed graphs.
We give the first polynomialtime algorithm for the problem.

Submitted: July 2018.
Reviewed: January 2019.
Revised: February 2019.
Accepted: February 2019.
Final: February 2019.
Published: February 2019.
Communicated by
Dorothea Wagner

Journal Supporters
