On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model

DOI10.1007/978-3-319-59605-1_2zbMath1430.68359arXiv1805.05448OpenAlexW2963030156MaRDI QIDQ4632199

Feifei Ma, Jian Zhang, Wencheng Wang, Sergey Bereg, Binhai Zhu

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.05448

zbMATH Keywords

matching problemundirected graphvertex cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the parameterized complexity of multiple-interval graph problems
• Parameterized complexity of finding regular induced subgraphs
• The parameterized complexity of the induced matching problem
• Computing minimum diameter color-spanning sets is hard
• On some geometric problems of color-spanning sets
• Parametrized complexity theory.
• Computing Minimum Diameter Color-Spanning Sets