scientific article; zbMATH DE number 7278106

DOI10.4230/LIPIcs.FSTTCS.2017.34zbMath1491.68145arXiv1702.07292MaRDI QIDQ5136326

No author found.

Publication date: 25 November 2020

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

PQ-treesnetwork constructionsubgraph connectivityordered connectivity constraints

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Cites Work

• Unnamed Item
• Equal-need sharing of a network under connectivity constraints
• Learning a hidden graph using \(O(\log n)\)queries per edge
• Optimally learning social networks with activations and suppressions
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• The clustering matroid and the optimal clustering tree
• Network construction with subgraph connectivity constraints
• The complete optimal stars-clustering-tree problem
• A general approach to online network optimization problems
• A threshold of ln n for approximating set cover
• Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
• The Online Set Cover Problem
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• Learning a Hidden Matching
• Online and Stochastic Survivable Network Design
• Inferring Social Networks from Outbreaks
• Learning a Hidden Subgraph
• Constructing scalable overlays for pub-sub with many topics