The conditional covering problem on unweighted interval graphs with nonuniform coverage radius

DOI10.1007/s11786-011-0106-1zbMath1262.05146MaRDI QIDQ1948610

Akul Rana, Anita Pal, Madhumangal Pal

Publication date: 24 April 2013

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

Full work available at URL: https://doi.org/10.1007/s11786-011-0106-1

zbMATH Keywords

distance; analysis of algorithms; design of algorithms; interval graph; maximal clique; conditional covering problem; minimum cardinality vertex set

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

An optimal algorithm to find minimum k-hop dominating set of interval graphs, A linear time algorithm to compute square of interval graphs and their colouring, \(L(2,1)\)-labeling of interval graphs, Optimization in business strategy as a part of sustainable economic growth using clique covering of fuzzy graphs

Cites Work

• On conditional covering problem
• Conditional covering: greedy heuristics and computational results
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Facility location on a tree with maximum distance constraints
• New heuristics for the conditional covering problem
• Incidence matrices and interval graphs
• An Analysis of Network Location Problems with Distance Constraints
• Algorithms for solving the conditional covering problem on paths
• Dynamic programming algorithms for the conditional covering problem on path and extended star graphs
• A dynamic programming algorithm for the conditional covering problem on tree graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item