The conditional covering problem on unweighted interval graphs with nonuniform coverage radius
From MaRDI portal
Publication:1948610
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
distance; analysis of algorithms; design of algorithms; interval graph; maximal clique; conditional covering problem; minimum cardinality vertex set
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