Optimization problems in multiple-interval graphs

DOI10.1145/1721837.1721856MaRDI QIDQ2930319zbMATH OpenOpenAlexFDO

Authors Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1721837.1721856

zbMATH Keywords

approximation algorithmsmaximum cliqueminimum dominating setminimum vertex covermultiple-interval graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• Optimization problems in multiple-interval graphs
• The maximum clique problem in multiple interval graphs
• The maximum clique problem in multiple interval graphs (extended abstract)
• On the parameterized complexity of multiple-interval graph problems
• Generalized vertex covering in interval graphs

Cited in

(32)

• Interval-parameter optimization problems on graphs
• Generalized vertex covering in interval graphs
• On dominating set of some subclasses of string graphs
• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
• Approximability and parameterized complexity of multicover by \(c\)-intervals
• Shiftable intervals
• Shiftable intervals
• Parameterized complexity in multiple-interval graphs: domination
• Optimization problems in multiple-interval graphs
• scientific article; zbMATH DE number 4179413 (Why is no real title available?)
• Optimization problems in multiple subtree graphs
• Online selection of intervals and t-intervals
• Optimization problems in dotted interval graphs
• Improved algorithm for resource allocation problems
• Approximation algorithms for intersection graphs
• Approximating dominating set on intersection graphs of rectangles and L-frames
• Algorithms for intersection graphs for \(t\)-intervals and \(t\)-pseudodisks
• Optimization problems in dotted interval graphs
• The maximum clique problem in multiple interval graphs (extended abstract)
• Optimization problems in multiple subtree graphs
• Optimality program in segment and string graphs
• Temporal interval cliques and independent sets
• Mobility offer allocations in corporate settings
• A graph-theoretic barcode ordering model for linked-reads
• Dominating set is fixed parameter tractable in claw-free graphs
• Recognizing unit multiple interval graphs is hard
• Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
• Recognizing unit multiple intervals is hard
• Generalizing Roberts' characterization of unit interval graphs
• Multistage graph problems on a global budget
• Three ways to cover a graph

This page was built for publication: Optimization problems in multiple-interval graphs

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