Temporal unit interval independent sets
From MaRDI portal
Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) 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) Approximation algorithms (68W25)
Cites work
- A Characterization of Comparability Graphs and of Interval Graphs
- A note on the consecutive ones submatrix problem.
- A structure theorem for the consecutive 1's property
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithms – ESA 2005
- An introduction to temporal graphs: an algorithmic perspective
- Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
- Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes
- Computing maximal cliques in link streams
- Computing maximum matchings in temporal graphs.
- Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
- Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 1185295 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1303579 (Why is no real title available?)
- scientific article; zbMATH DE number 2065154 (Why is no real title available?)
- scientific article; zbMATH DE number 3307330 (Why is no real title available?)
- Independent Sets in Circular-Arc Graphs
- Obtaining matrices with the consecutive ones property by row deletions
- On the exploration of time-varying networks
- On the parameterized complexity of multiple-interval graph problems
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- Parameterized and Exact Computation
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- Reducibility among combinatorial problems
- Scheduling Split Intervals
- Sliding window temporal graph coloring
- Temporal graph classes: a view through temporal separators
- Temporal vertex cover with a sliding time window
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The intersection graphs of subtrees in trees are exactly the chordal graphs
This page was built for publication: Temporal unit interval independent sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7395556)
