Balanced independent and dominating sets on colored interval graphs
DOI10.1007/978-3-030-67731-2_7zbMath1490.68147arXiv2003.05289OpenAlexW3127735748MaRDI QIDQ831789
Martin Nöllenburg, Guangping Li, Jan-Henrik Haunert, Fabian Klute, Sujoy Bhore
Publication date: 24 March 2022
Full work available at URL: https://arxiv.org/abs/2003.05289
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- A linear kernel for planar red-blue dominating set
- \(k\)-domination and \(k\)-independence in graphs: A survey
- On approximating the minimum independent dominating set
- A simplified NP-complete satisfiability problem
- Interval scheduling and colorful independent sets
- Counting the number of independent sets in chordal graphs
- Label placement by maximum independent set in rectangles
- Point labeling with sliding labels
- The maximum clique problem
- Algorithmic graph theory and perfect graphs
- Algorithm and hardness results on liar's dominating set and \({k}\)-tuple dominating set
- Representation of a finite graph by a set of intervals on the real line
- Finding a Maximum Clique in an Arbitrary Graph
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- PTAS for geometric hitting set problems via local search
- Approximation algorithms for maximum independent set of pseudo-disks
- Term Rewriting and Applications
- Optimizing active ranges for consistent dynamic map labeling
This page was built for publication: Balanced independent and dominating sets on colored interval graphs
