3 papers
cs.CC2026
Solution independence and self-referential instances
Guangyan Zhou, Bin Wang, Jianxin Wang +1
In this paper, we investigate the hitting set problem and demonstrate that solution independence is the crucial property underlying the construction of self-referential instances.…
math.CO2024
On well (edge) dominated and equimatchable strong product graphs
Yixin Cao, Guiqiang Mou, Jianxin Wang
A graph is well-(edge-)dominated if every minimal (edge) dominating set is minimum. A graph is equimatchable if every maximal matching is maximum. We study these concepts on strong…
cs.DS2024
Minimum sum vertex cover: kernelization and parameterized algorithms
Yixin Cao, Ling Gai, Jingyi Liu +1
Given an ordering of the vertices of a graph, the cost of covering an edge is the smaller number of its two ends. The minimum sum vertex cover problem asks for an ordering that min…