Graph-Theoretic Concepts in Computer Science

DOI10.1007/11604686MaRDI QIDQ5897569zbMATH OpenFDO

Authors Erik Jan van Leeuwen

Publication date 1 November 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• Distributed Approximation Algorithms in Unit-Disk Graphs
• Simple heuristics for unit disk graphs
• Linear time approximation for dominating sets and independent dominating sets in unit disk graphs

Cited in

(26)

• Optimization problems in dotted interval graphs
• Minimum vertex cover in rectangle graphs
• Good Quality Virtual Realization of Unit Ball Graphs
• Connected dominating sets on dynamic geometric graphs
• Better Approximation Schemes for Disk Graphs
• Two generalizations of proper coloring: hardness and approximability
• ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
• Plane hop spanners for unit disk graphs: simpler and better
• Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
• Reducing the diameter of a unit disk graph via node addition
• Cubicity and bandwidth
• Near-optimal algorithms for shortest paths in weighted unit-disk graphs
• Distributed Approximation Algorithms in Unit-Disk Graphs
• Distributed Approximations for Packing in Unit-Disk Graphs
• Algorithms for the minimum weight k-fold (connected) dominating set problem
• Efficient independent set approximation in unit disk graphs
• Approximating 2-cliques in unit disk graphs
• Improved algorithm for maximum independent set on unit disk graph
• Simple heuristics for unit disk graphs
• Approximate Distance Queries in Disk Graphs
• Faster approximation for maximum independent set on unit disk graph
• On the recognition of unit disk graphs and the distance geometry problem with ranges
• On the cubicity of AT-free graphs and circular-arc graphs
• Structure of polynomial-time approximation
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• scientific article; zbMATH DE number 7236428 (Why is no real title available?)

This page was built for publication: Graph-Theoretic Concepts in Computer Science

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