Cover Image

An Improved Kernel and Parameterized Algorithm for Almost Induced Matching

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Liu, Yuxi, Xiao, Mingyu
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth
by: Liu, Yuxi, et al.
Published: (2026)

A Refined Kernel for $d$-Hitting Set
by: Liu, Yuxi, et al.
Published: (2025)

Linear Kernels for $l$-Exact Component Order Connectivity
by: Liu, Yuxi, et al.
Published: (2026)

Faster Parameterized Vertex Multicut
by: Chu, Huairui, et al.
Published: (2026)

A Simplified Parameterized Algorithm for Directed Feedback Vertex Set
by: Xiong, Ziliang, et al.
Published: (2024)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
by: Zhao, Jingyang, et al.
Published: (2025)

Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than $3^k$
by: Liu, Yuxi, et al.
Published: (2024)

Algorithms for Parameterized String Matching with Mismatches
by: Saha, Apurba, et al.
Published: (2024)

An Improved Approximation Algorithm for Metric Triangle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
by: Zhao, Jingyang, et al.
Published: (2022)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
by: Zhao, Jingyang, et al.
Published: (2025)

An Improved Algorithm for a Bipartite Traveling Tournament in Interleague Sports Scheduling
by: Zhao, Jingyang, et al.
Published: (2025)

The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

Efficient Kernelization Algorithm for Bipartite Graph Matching
by: Wu, Guang, et al.
Published: (2024)

Structural Parameterizations for Induced and Acyclic Matching
by: Lampis, Michael, et al.
Published: (2025)

Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
by: Goyal, Dishant, et al.
Published: (2024)

Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
by: Zhao, Jingyang, et al.
Published: (2023)

Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximations for Dial-a-Ride Problems
by: Zhao, Jingyang, et al.
Published: (2026)

(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs
by: Gahlawat, Harmender, et al.
Published: (2025)

A Faster Deterministic Algorithm for Kidney Exchange via Representative Set
by: Tian, Kangyi, et al.
Published: (2026)

Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees
by: Zhao, Jingyang, et al.
Published: (2023)

Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

Almost Tight Bounds for Online Hypergraph Matching
by: Tröbst, Thorben, et al.
Published: (2024)

Improved Kernelization and Fixed-parameter Algorithms for Bicluster Editing
by: Lafond, Manuel
Published: (2024)

Approximating Maximum Matching Requires Almost Quadratic Time
by: Behnezhad, Soheil, et al.
Published: (2024)

New Algorithms for #2-SAT and #3-SAT
by: Peng, Junqiang, et al.
Published: (2025)

Improved and Parameterized Algorithms for Online Multi-level Aggregation: A Memory-based Approach
by: Turoczy, Alexander, et al.
Published: (2025)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
by: Fomin, Fedor V., et al.
Published: (2025)

An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments
by: Bai, Tian
Published: (2025)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Parameterized Algorithms for the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2026)

Subexponential Parameterized Algorithms for Hitting Subgraphs
by: Lokshtanov, Daniel, et al.
Published: (2024)

Parameterized Algorithms for Computing Pareto Sets
by: Könen, Joshua, et al.
Published: (2025)

Parameterized Algorithms for Computing MAD Trees
by: Breitkopf, Tom-Lukas, et al.
Published: (2026)

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

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
by: Bergougnoux, Benjamin, et al.
Published: (2023)

Parameterized Algorithms for the Steiner Arborescence Problem on a Hypercube
by: Mahapatra, Sugyani, et al.
Published: (2021)