On some matching problems under the color-spanning model

DOI10.1016/j.tcs.2018.08.008zbMath1429.68318OpenAlexW2886997252MaRDI QIDQ2319899

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

Publication date: 20 August 2019

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.08.008

zbMATH Keywords

NP-completenesscomputational geometrymatching algorithmsfixed-parameter tractabilityFPT algorithmscolor-spanning model

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)

Related Items

Online \(k\)-color spanning disk problems, Dispersing and grouping points on planar segments, Minimum diameter color-spanning sets revisited, Rainbow polygons for colored point sets in the plane

Cites Work

• On the parameterized complexity of multiple-interval graph problems
• Parameterized complexity of finding regular induced subgraphs
• The parameterized complexity of the induced matching problem
• Unit disk graphs
• 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
• Algorithms for two bottleneck optimization problems
• Algorithms – ESA 2005
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item