Minimum Violation Vertex Maps and Their Applications to Cut Problems
From MaRDI portal
Publication:5138968
DOI10.1137/19M1290899zbMath1453.05072OpenAlexW3094217343MaRDI QIDQ5138968
Chao Xu, Ken-ichi Kawarabayashi
Publication date: 4 December 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1290899
Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of surjective homomorphism problems-a survey
- An algebraic hardness criterion for surjective constraint satisfaction.
- Blocking optimal arborescences
- Efficient algorithms for the problems of enumerating cuts by non-decreasing weights
- Blocking unions of arborescences
- Parameterized complexity of length-bounded cuts and multicuts
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- Beating the 2-approximation factor for global bicut
- A dichotomy for minimum cost graph homomorphisms
- Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
- Approximation of Minimum Cost Homomorphisms
- Absolute Retracts and Varieties of Reflexive Graphs
- The Complexity of Finite-Valued CSPs
- Length-bounded cuts and flows
- Skew Bisubmodularity and Valued CSPs
- LP Relaxation and Tree Packing for Minimum $k$-Cut
- The approximability of MAX CSP with fixed-value constraints
- Approximation algorithms for classification problems with pairwise relationships
- Approximation Algorithms for Graph Homomorphism Problems
- Diameter increase caused by edge deletion
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- The Complexity of Multiterminal Cuts
- Approximating Multicut and the Demand Graph
- Multiway cuts in directed and node weighted graphs
- The complexity of finding maximum disjoint paths with length constraints
- The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs
- Testing the Complexity of a Valued CSP Language
- Improved Hardness for Cut, Interdiction, and Firefighter Problems
- The Karger-Stein algorithm is optimal for k-cut
- The Complexity of Boolean Surjective General-Valued CSPs
- The number of minimum k -cuts: improving the Karger-Stein bound
- The Approximability of Three-valued MAX CSP
- The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
- Discrete convexity and polynomial solvability in minimum 0-extension problems
This page was built for publication: Minimum Violation Vertex Maps and Their Applications to Cut Problems
