Optimization problems in dotted interval graphs
From MaRDI portal
Publication:400519
DOI10.1016/j.dam.2014.04.014zbMath1298.05172OpenAlexW2079170078MaRDI QIDQ400519
Dror Rawitz, Julián Mestre, Danny Hermelin
Publication date: 22 August 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2014.04.014
Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Characterization of 2-path signed network, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization problems in multiple subtree graphs
- Minimum vertex cover in rectangle graphs
- Approximating minimum coloring and maximum independent set in dotted interval graphs
- Approximation algorithm for coloring of dotted interval graphs
- On the parameterized complexity of multiple-interval graph problems
- Graph minors. I. Excluding a forest
- Linear time algorithms on circular-arc graphs
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Label placement by maximum independent set in rectangles
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- k-Gap Interval Graphs
- Optimization problems in multiple-interval graphs
- Dotted interval graphs
- Stability in circular arc graphs
- The Complexity of Coloring Circular Arcs and Chords
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Scheduling Split Intervals
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Better Approximation Schemes for Disk Graphs
- Graph-Theoretic Concepts in Computer Science
