Finding a maximum-weight convex set in a chordal graph

DOI10.7155/JGAA.00488zbMATH Open1407.05218arXiv1806.09992OpenAlexW2962752353MaRDI QIDQ3121516FDOQ3121516

Authors: Jean Cardinal, Jean-Paul Doignon, Keno Merckx 

Publication date: 18 March 2019

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

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 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.

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

Recommendations

• scientific article; zbMATH DE number 4198027
• Packing \(r\)-cliques in weighted chordal graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Counting the number of independent sets in chordal graphs
• Maximal chordal subgraphs

zbMATH Keywords

combinatorial optimizationchordal graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Topics in Intersection Graph Theory
• Title not available (Why is that?)
• On local convexity in graphs
• Cooperative games on antimatroids
• Algorithmic graph theory and perfect graphs
• Incidence matrices and interval graphs
• Convexity in Graphs and Hypergraphs
• The theory of convex geometries
• A new approach to the maximum-flow problem
• Title not available (Why is that?)
• The clique-separator graph for chordal graphs
• Partition numbers for trees and ordered sets
• Learning spaces. Interdisciplinary applied mathematics
• Geo-graphs: an efficient model for enforcing contiguity and hole constraints in planar graph partitioning
• Maximal Closure of a Graph and Applications to Combinatorial Problems
• Title not available (Why is that?)
• Finding minimum area \(k\)-gons
• Counting clique trees and computing perfect elimination schemes in parallel
• Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
• A Selection Problem of Shared Fixed Costs and Network Flows
• On finite convexity spaces induced by sets of paths in graphs
• Hull numbers of path convexities on graphs
• Greedoids
• Choice functions and abstract convex geometries
• An algorithmic characterization of antimatroids
• Optimizing constrained subtrees of trees
• Path-closed sets
• Induced path transit function, monotone and Peano axioms
• Title not available (Why is that?)
• Gray codes for AT-free orders via antimatroids

Cited In (3)

• Path-closed sets
• Finding a maximum set of independent chords in a circle
• Packing \(r\)-cliques in weighted chordal graphs

Uses Software

• Algorithm 447

This page was built for publication: Finding a maximum-weight convex set in a chordal graph

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