Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs

DOI10.1016/J.TCS.2026.116173MaRDI QIDQ7347260zbMATH OpenFDO

Authors Shinwoo An, Yeonsu Chang, Kyungjin Cho, O-joung Kwon, Myounghwan Lee, Eunjin Oh, Hyeonjun Shin

Publication date 14 September 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.116173

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• \(k\)-NLC graphs and polynomial algorithms
• 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
• Approximating clique-width and branch-width
• Breaking the PPSZ barrier for unique 3-SAT
• Clique-width minimization is NP-hard
• Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
• Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth
• Dominating sets for split and bipartite graphs
• Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth
• Edge dominating set and colorings on graphs with fixed clique-width
• Fast FPT-approximation of branchwidth
• Graph minors. XX: Wagner's conjecture
• Graph-Theoretic Concepts in Computer Science
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• How many clues to give? A bilevel formulation for the minimum Sudoku clue problem
• scientific article; zbMATH DE number 1208724 (Why is no real title available?)
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• Intractability of clique-width parameterizations
• Linear time solvable optimization problems on graphs of bounded clique-width
• On approximating the minimum independent dominating set
• On the clique-width of graph with few \(P_{4}\)'s
• On the clique-width of some perfect graph classes
• On the Computational Complexity of the Forcing Chromatic Number
• On the Relationship Between Clique-Width and Treewidth
• PPSZ for general \(k\)-SAT -- making Hertli's analysis simpler and 3-SAT faster
• Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover
• Restricted power domination and zero forcing problems
• SATLIB: An online resource for research on SAT
• Simple linear time recognition of unit interval graphs
• The complexity of pre-assignment problem for unique minimum vertex cover on bipartite graphs
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• The ellipsoid method and its consequences in combinatorial optimization
• The fewest clues problem
• The fewest clues problem of Picross 3D
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The relationship between \(k\)-forcing and \(k\)-power domination
• Tight double exponential lower bounds
• TSPLIB—A Traveling Salesman Problem Library
• Unique maximum matching algorithms
• Upper bounds to the clique width of graphs

This page was built for publication: Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs

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