Algorithms – ESA 2005

DOI10.1007/11561071MaRDI QIDQ5475855zbMATH OpenOpenAlexFDO

Authors Dániel Marx

Publication date 27 June 2006

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

Full work available at URL https://doi.org/10.1007/11561071

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Polynomial-time approximation schemes for geometric graphs
• Better Approximation Schemes for Disk Graphs
• On the efficiency of polynomial time approximation schemes
• Graph-Theoretic Concepts in Computer Science

Cited in

(39)

• Optimality of geometric local search
• Dispersing and grouping points on planar segments
• The parameterized hardness of the \(k\)-center problem in transportation networks
• Maximum bipartite subgraphs of geometric intersection graphs
• On approximating string selection problems with outliers
• Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
• scientific article; zbMATH DE number 7278055 (Why is no real title available?)
• Temporal interval cliques and independent sets
• A tight analysis of geometric local search
• Fractal dimension and lower bounds for geometric problems
• FO model checking on geometric graphs
• scientific article; zbMATH DE number 7236474 (Why is no real title available?)
• On some matching problems under the color-spanning model
• Twin-width II: small classes
• Computational complexity for the problem of optimal intersection of straight line segments by disks
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• Fixed-parameter tractability and lower bounds for stabbing problems
• On the parameterized complexity of \(d\)-dimensional point set pattern matching
• Linear-time approximation algorithms for unit disk graphs
• FO model checking of geometric graphs
• Consensus patterns (probably) has no EPTAS
• Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
• Computing list homomorphisms in geometric intersection graphs
• Minimum vertex cover in rectangle graphs
• Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
• Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
• Exact multi-covering problems with geometric sets
• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• On the parameterized complexity of multiple-interval graph problems
• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
• Parameterized complexity of induced graph matching on claw-free graphs
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• A unified model and algorithms for temporal map labeling
• Shifting strategy for geometric graphs without geometry
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• Unique covering problems with geometric sets
• Safe approximation and its relation to kernelization
• Parameterized complexity of geometric covering problems having conflicts
• The parameterized hardness of the \(k\)-center problem in transportation networks

This page was built for publication: Algorithms – ESA 2005

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