Maximum rooted connected expansion

DOI10.1016/J.TCS.2021.04.022MaRDI QIDQ2034397zbMATH OpenOpenAlexFDO

Authors Ioannis Lamprou, Russell Martin, Sven Schewe, Ioannis Sigalas, V. 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

approximationexpansiondominationPTASratioprefetching

Mathematics Subject Classification ID

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

Recommendations

• Maximum rooted connected expansion
• To satisfy impatient web surfers is hard
• Connected surveillance game
• scientific article; zbMATH DE number 1300393
• A Graph-Theoretic Game and Its Application to the k-Server Problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1323125 (Why is no real title available?)
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• Algorithmic graph theory and perfect graphs
• Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems
• Computing the isoperimetric number of a graph
• Connected surveillance game
• Dominating cliques in chordal graphs
• Expander graphs and their applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Graph classes with structured neighborhoods and algorithmic applications
• Isoperimetric numbers of graphs
• On an isoperimetric problem for Hamming graphs
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The splittance of a graph
• The vertex isoperimetric problem for the powers of the diamond graph
• To satisfy impatient web surfers is hard

Cited in

(1)

• Maximum rooted connected expansion

This page was built for publication: Maximum rooted connected expansion

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