Cover Image

Minimum sum vertex cover: kernelization and parameterized algorithms

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cao, Yixin, Gai, Ling, Liu, Jingyi, Wang, Jianxin
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximation and parameterized algorithms for covering disjointness-compliable set families
by: Nutov, Zeev, et al.
Published: (2025)

Faster parameterized algorithm for 3-Hitting Set
by: Tsur, Dekel
Published: (2025)

Minimum Sum Set Cover: Structures and Algorithm
by: Zhang, Zhongyi, et al.
Published: (2026)

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
by: Kobayashi, Yasuaki, et al.
Published: (2023)

A faster polynomial-space algorithm for Hamiltonian cycle parameterized by treedepth
by: Kratsch, Stefan
Published: (2026)

Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
by: An, Shinwoo, et al.
Published: (2024)

Kernelization for list $H$-coloring for graphs with small vertex cover
by: Piecyk, Marta, et al.
Published: (2025)

A faster algorithm for Vertex Cover parameterized by solution size
by: Harris, David G., et al.
Published: (2022)

A polynomial kernel for vertex deletion into bipartite permutation graphs
by: Derbisz, Jan
Published: (2021)

Efficient parameterized approximation
by: Kratsch, Stefan, et al.
Published: (2025)

Cluster Vertex Deletion on Chordal Graphs
by: Cao, Yixin, et al.
Published: (2026)

Complexity and Algorithm for the Matching vertex-cutset Problem
by: Li, Hengzhe, et al.
Published: (2025)

Exact Optimization for Minimum Dominating Sets
by: Zhu, Enqiang, et al.
Published: (2025)

Characterization of Circular-arc Graphs: II. McConnell Flipping
by: Cao, Yixin, et al.
Published: (2024)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
by: Korhonen, Tuukka, et al.
Published: (2024)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
by: Peng, Pan, et al.
Published: (2026)

On polynomial kernelization for Stable Cutset
by: Kratsch, Stefan, et al.
Published: (2024)

Improved 2-Approximate Shortest Paths for close vertex pairs
by: Gupta, Manoj
Published: (2025)

Toward Minimum Graphic Parity Networks
by: Cao, Yixin, et al.
Published: (2025)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
by: Henzinger, Monika, et al.
Published: (2024)

Parameterized and approximation algorithms for coverings points with segments in the plane
by: Kowalska, Katarzyna, et al.
Published: (2024)

Maximizing the Minimum Eigenvalue in Constant Dimension
by: Brown, Adam, et al.
Published: (2024)

Width Parameters for Minimum Flow Decomposition
by: Grigorjew, Andreas, et al.
Published: (2024)

Faster Pseudo-Deterministic Minimum Cut
by: Kenneth-Mordoch, Yotam
Published: (2026)

Minimum Temporal Spanners in Happy Graphs
by: Casteigts, Arnaud, et al.
Published: (2026)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Thin Trees for Near Minimum Cuts
by: Klein, Nathan, et al.
Published: (2026)

Faster Global Minimum Cut with Predictions
by: Moseley, Benjamin, et al.
Published: (2025)

Learning Minimum Linear Arrangement of Cliques and Lines
by: Dallot, Julien, et al.
Published: (2024)

Parameterized Algorithms for Minimum Sum Vertex Cover
by: Aute, Shubhada, et al.
Published: (2024)

Simple Length-Constrained Minimum Spanning Trees
by: Hershkowitz, D Ellis, et al.
Published: (2024)

Planar Length-Constrained Minimum Spanning Trees
by: Hershkowitz, D Ellis, et al.
Published: (2025)

Connectivity-Preserving Minimum Separator in AT-free Graphs
by: Kenig, Batya
Published: (2025)

Improving Pinwheel Density Bounds for Small Minimums
by: Mishra, Ahan, et al.
Published: (2025)

Near-Optimal Minimum Cuts in Hypergraphs at Scale
by: Chhabra, Adil, et al.
Published: (2025)

Minimum-Peak-Cost Flows Over Time
by: Anapolska, Mariia, et al.
Published: (2025)

Selective algorithm processing of subset sum distributions
by: Dawes, Nick
Published: (2024)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
by: Jiang, Yonggang, et al.
Published: (2025)

Fast decremental tree sums in forests
by: Berendsohn, Benjamin Aram, et al.
Published: (2026)

Edge-Minimum Walk of Modular Length in Polynomial Time
by: Amarilli, Antoine, et al.
Published: (2024)