Maximum rooted connected expansion

DOI10.1016/j.tcs.2021.04.022zbMath1506.68076OpenAlexW2887754464MaRDI QIDQ2034397

Sven Schewe, Ioannis Sigalas, Russell Martin, Ioannis Lamprou, Vassilios Zissimopoulos

Publication date: 22 June 2021

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9607/

zbMATH Keywords

expansionapproximationprefetchingdominationPTASratio

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• The splittance of a graph
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On an isoperimetric problem for Hamming graphs
• Dominating cliques in chordal graphs
• Algorithmic graph theory and perfect graphs
• Computing the isoperimetric number of a graph
• Connected surveillance game
• To satisfy impatient web surfers is hard
• The vertex isoperimetric problem for the powers of the diamond graph
• Isoperimetric numbers of graphs
• Expander graphs and their applications
• Saving an epsilon
• A General Approximation Technique for Constrained Forest Problems
• Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems

This page was built for publication: Maximum rooted connected expansion