A Tractable Class of Binary VCSPs via M-Convex Intersection

DOI10.1145/3329862zbMath1454.68058arXiv1801.02199OpenAlexW3122931165WikidataQ127471084 ScholiaQ127471084MaRDI QIDQ4972691

Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, Stanislav Živný

Publication date: 25 November 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

discrete convex analysisvalued constraint satisfaction problemsM-convexity

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Reconstructing phylogenetic trees from multipartite quartet systems, Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hybrid tractability of valued constraint problems
• Convexity and Steinitz's exchange property
• Pseudo-Boolean optimization
• Valuated matroids: A new look at the greedy algorithm
• A fast algorithm for constructing trees from distance matrices
• Valuated matroids
• The complexity of reconstructing trees from qualitative characters and subtrees
• Discrete convex analysis
• Discrete convexity in joint winner property
• The quadratic M-convexity testing problem
• \(M\)-convex functions and tree metrics
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Quadratic M-convex and L-convex functions
• A geometric study of the split decomposition
• Nonserial dynamic programming
• Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
• Recent Developments in Discrete Convex Analysis
• Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection.
• Discrete Convex Analysis
• L-CONVEXITY ON GRAPH STRUCTURES
• Valuated Matroid Intersection I: Optimality Criteria
• Valuated Matroid Intersection II: Algorithms
• The Complexity of Valued Constraint Satisfaction Problems
• Hybrid Tractable Classes of Constraint Problems
• The Power of Linear Programming for General-Valued CSPs
• The Complexity of General-Valued CSPs
• Geometry of cuts and metrics
• Combinatorial optimization. Theory and algorithms
• Matrices and matroids for systems analysis
• Discrete convexity and polynomial solvability in minimum 0-extension problems