On some matching problems under the color-spanning model

DOI10.1016/J.TCS.2018.08.008MaRDI QIDQ2319899zbMATH OpenOpenAlexFDO

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

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

color-spanning modelcomputational geometryfixed-parameter tractabilityFPT algorithmsmatching algorithmsNP-completeness

Mathematics Subject Classification ID

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

Recommendations

• On the fixed-parameter tractability of some matching problems under the color-spanning model
• Minimum diameter color-spanning sets revisited
• On some geometric problems of color-spanning sets
• On some geometric problems of color-spanning sets
• Matching colored points with rectangles

Cites work

• Algorithms for two bottleneck optimization problems
• Algorithms – ESA 2005
• Computing minimum diameter color-spanning sets
• Computing minimum diameter color-spanning sets is hard
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1875422 (Why is no real title available?)
• On some geometric problems of color-spanning sets
• On the parameterized complexity of multiple-interval graph problems
• Parameterized complexity of finding regular induced subgraphs
• Parametrized complexity theory.
• The parameterized complexity of the induced matching problem
• Unit disk graphs

Cited in

(8)

• Budgeted colored matching problems
• Minimum diameter color-spanning sets revisited
• Rainbow polygons for colored point sets in the plane
• Dispersing and grouping points on planar segments
• On the fixed-parameter tractability of some matching problems under the color-spanning model
• Online \(k\)-color spanning disk problems
• The 2-mixed-center color spanning problem
• The 2-attractor problem is NP-complete

This page was built for publication: On some matching problems under the color-spanning model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2319899)