An Optimal Algorithm to Solve 2-Neighbourhood Covering Problem on Interval Graphs

DOI10.1080/00207160211921MaRDI QIDQ4780532zbMATH OpenOpenAlexFDO

Authors Sukumar Mondal, Madhumangal Pal, Tapan K. Pal

Publication date 2002

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160211921

zbMATH Keywords

interval tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An optimal algorithm to solve 2-neighbourhood covering problem on circular-arc graphs
• An optimal algorithm to solve 2-neighbourhood covering problem on trapezoid graphs
• The \(k\)-neighbourhood-covering problem on interval graphs
• The 2-neighbourhood covering problem on permutation graphs
• Generalized vertex covering in interval graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• k-Neighborhood-Covering and -Independence Problems for Chordal Graphs
• Algorithmic Aspects of Neighborhood Numbers
• Neighborhood perfect graphs
• One-dimensional logic gate assignment and interval graphs
• Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph
• THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS

Cited in

(10)

• An optimal algorithm to solve 2-neighbourhood covering problem on trapezoid graphs
• The \(k\)-neighbourhood-covering problem on interval graphs
• An optimal algorithm to solve 2-neighbourhood covering problem on circular-arc graphs
• Minimum \(r\)-neighborhood covering set of permutation graphs
• Minimum line-neighbourhood set of an interval graph -- a linear time algorithm
• The interval-merging problem
• An optimal algorithm to find minimum k-hop dominating set of interval graphs
• The 2-neighbourhood covering problem on permutation graphs
• L(2,1)-labeling of interval graphs
• Minimum 2-tuple dominating set of an interval graph

This page was built for publication: An Optimal Algorithm to Solve 2-Neighbourhood Covering Problem on Interval Graphs

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