Geodesic
Finding a Maximum-Weight Convex Set in a Chordal Graph
Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 2, pp. 167-190.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 maximum-weight convex subset of a given vertex-weighted 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 polynomial-time algorithm for the problem.
DOI : 10.7155/jgaa.00488
Keywords: chordal graph, minimum-weight convex set, partially ordered set, antimatroid 
@article{JGAA_2019_23_2_a2,
     author = {Jean Cardinal and Jean-Paul Doignon and Keno Merckx},
     title = {Finding a {Maximum-Weight} {Convex} {Set} in a {Chordal} {Graph}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {167--190},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2019},
     doi = {10.7155/jgaa.00488},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00488/}
}
TY  - JOUR
AU  - Jean Cardinal
AU  - Jean-Paul Doignon
AU  - Keno Merckx
TI  - Finding a Maximum-Weight Convex Set in a Chordal Graph
JO  - Journal of Graph Algorithms and Applications
PY  - 2019
SP  - 167
EP  - 190
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00488/
DO  - 10.7155/jgaa.00488
LA  - en
ID  - JGAA_2019_23_2_a2
ER  - 
%0 Journal Article
%A Jean Cardinal
%A Jean-Paul Doignon
%A Keno Merckx
%T Finding a Maximum-Weight Convex Set in a Chordal Graph
%J Journal of Graph Algorithms and Applications
%D 2019
%P 167-190
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00488/
%R 10.7155/jgaa.00488
%G en
%F JGAA_2019_23_2_a2
Jean Cardinal; Jean-Paul Doignon; Keno Merckx. Finding a Maximum-Weight Convex Set in a Chordal Graph. Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 2, pp. 167-190. doi : 10.7155/jgaa.00488. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00488/

Cité par Sources :