Temporal interval cliques and independent sets

DOI10.1016/j.tcs.2023.113885arXiv2112.06172MaRDI QIDQ6039892

Hendrik Molter, Danny Hermelin, Rolf Niedermeier, Yuval Itzhaki

Publication date: 23 May 2023

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

Full work available at URL: https://arxiv.org/abs/2112.06172

zbMATH Keywords

interval graphsalgorithms and complexityorder preservationtemporal graphsvertex orderings

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• Triangulated neighborhoods in even-hole-free graphs
• Computing maximal cliques in link streams
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• On the parameterized complexity of multiple-interval graph problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A note on the consecutive ones submatrix problem.
• On the exploration of time-varying networks
• Temporal vertex cover with a sliding time window
• Sliding window temporal graph coloring
• Obtaining matrices with the consecutive ones property by row deletions
• The maximum clique problem in multiple interval graphs
• A structure theorem for the consecutive 1's property
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Independent Sets in Circular-Arc Graphs
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• Complex Networks and Link Streams for the Empirical Analysis of Large Software
• Parameterized and Exact Computation
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Scheduling Split Intervals
• Algorithms – ESA 2005
• A Characterization of Comparability Graphs and of Interval Graphs
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Computing maximum matchings in temporal graphs.
• Temporal graph classes: a view through temporal separators
• On finding separators in temporal split and permutation graphs

This page was built for publication: Temporal interval cliques and independent sets