Polynomial time algorithm for k-vertex-edge dominating problem in interval graphs

DOI10.1007/S10878-022-00982-8MaRDI QIDQ2111523zbMATH OpenOpenAlexFDO

Authors Peng Li, Aifa Wang

Publication date 17 January 2023

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-022-00982-8

zbMATH Keywords

\(k\)-vertex-edge dominationdouble vertex-edge dominationinterval graphspolynomial time algorithmvertex-edge domination

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs
• On the algorithmic complexity of double vertex-edge domination in graphs
• A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs
• Double vertex-edge domination in graphs: complexity and algorithms
• A unified approach to domination problems on interval graphs

Cites work

• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• A unified approach to domination problems on interval graphs
• Algorithmic graph theory and perfect graphs
• Bounds on the vertex-edge domination number of a tree
• Double vertex-edge domination
• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• scientific article; zbMATH DE number 4045800 (Why is no real title available?)
• scientific article; zbMATH DE number 1057882 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs
• Results on vertex-edge and independent vertex-edge domination
• Spanning connectedness and Hamiltonian thickness of graphs and interval graphs
• The longest cycle problem is polynomial on interval graphs
• Total vertex-edge domination
• Vertex-edge domination
• Vertex-edge domination in graphs
• Vertex-edge domination in graphs

Cited in

(5)

• On \(k\)-vertex-edge domination of graph
• Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs
• Edge-vertex domination on interval graphs
• The k edge-vertex domination problem
• Algorithmic study on liar's vertex-edge domination problem

This page was built for publication: Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs

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