A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs

DOI10.1007/S11590-018-1371-6zbMATH Open1429.90062OpenAlexW2905339563WikidataQ128758713 ScholiaQ128758713MaRDI QIDQ2329655FDOQ2329655

Authors: M. Lalou, H. Kheddouci 

Publication date: 18 October 2019

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-018-1371-6

Recommendations

• Component-cardinality-constrained critical node problem in graphs
• Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
• A fast greedy algorithm for the critical node detection problem
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Detecting critical nodes in sparse graphs

zbMATH Keywords

dynamic programminggraph connectivitycritical nodesgraph separatorsbipartite permutation graphscomplete bipartite decomposition

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39)

Cites Work

• Title not available (Why is that?)
• A faster algorithm for betweenness centrality*
• Automata, Languages and Programming
• Detecting critical nodes in sparse graphs
• Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• Branch and cut algorithms for detecting critical nodes in undirected graphs
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Exact identification of critical nodes in sparse networks via new compact formulations
• The vertex separator problem: a polyhedral investigation
• Component-cardinality-constrained critical node problem in graphs
• An integer programming framework for critical elements detection in graphs
• Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
• Node-and edge-deletion NP-complete problems
• Complexity of the critical node problem over trees
• Bipartite permutation graphs
• Cardinality-Constrained Critical Node Detection Problem
• The critical node detection problem in networks: a survey
• A randomized algorithm with local search for containment of pandemic disease spread
• Random generation and enumeration of bipartite permutation graphs
• Disconnecting graphs by removing vertices: a polyhedral approach
• A preliminary analysis of the distance based critical node problem
• Parameterized complexity of critical node cuts
• Linear structure of bipartite permutation graphs and the longest path problem
• Complexity and approximability of the \(k\)-way vertex cut
• Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem

Cited In (11)

• EIA-CNDP: an exact iterative algorithm for critical node detection problem
• Component-cardinality-constrained critical node problem in graphs
• Complexity of the multilevel critical node problem
• Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
• Modeling the spread of infectious diseases through influence maximization
• A linear time algorithm for finding all hinge vertices of a permutation graph
• Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items
• Title not available (Why is that?)
• Acyclically pushable bipartite permutation digraphs: an algorithm
• The connected critical node problem
• A New Algorithm for Finding a Pseudoperipheral Node in a Graph

This page was built for publication: A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs

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