Complexity and algorithms for constant diameter augmentation problems

DOI10.1016/j.tcs.2021.05.020OpenAlexW3164510505MaRDI QIDQ2072060

Yanyan Li

Publication date: 1 February 2022

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

Full work available at URL: https://arxiv.org/abs/2010.00273

zbMATH Keywords

polynomial algorithmNP-completegraph diameterblocker problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

In memory of Jérôme Monnot ⋮ Reducing the vertex cover number via edge contractions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum edge blocker dominating set problem
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• The most vital nodes with respect to independent set and vertex cover
• Blockers for the stability number and the chromatic number
• Augmenting graphs to minimize the diameter
• Diameter critical graphs
• On short paths interdiction problems: Total and node-wise limited interdiction
• Blockers and transversals
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• The node-deletion problem for hereditary properties is NP-complete
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• Graphs with small diameter after edge deletion
• Blocking optimal structures
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• On the NP-hardness of edge-deletion and -contraction problems
• A survey on the missing Moore graph
• The parametric complexity of graph diameter augmentation
• Augmenting forests to meet odd diameter requirements
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Length-bounded cuts and flows
• Diameter increase caused by edge deletion
• Minimum vertex blocker clique problem
• Reducibility among Combinatorial Problems
• Diameter bounds for altered graphs
• Obtaining a Bipartite Graph by Contracting Few Edges
• There is No Irregular Moore Graph
• Diameters in graphs

This page was built for publication: Complexity and algorithms for constant diameter augmentation problems