Approximation Algorithms via Contraction Decomposition

Approximation Algorithms via Contraction Decomposition

http://www.springerlink.com/content/h96773m010737357/fulltext.pdf

Dades bibliogràfiques
Autors principals:	Hajiaghayi, Mohammad Taghi, Demaine, Erik D., Mohar, Bojan
Altres autors:	Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format:	Article
Idioma:	en_US
Publicat:	Bolyai Society/Springer-Verlag 2011
Accés en línia:	http://hdl.handle.net/1721.1/63808 https://orcid.org/0000-0003-3803-5703

Ítems similars

Contraction decomposition in h-minor-free graphs and algorithmic applications
per: Demaine, Erik D., et al.
Publicat: (2012)

Decomposition, approximation, and coloring of odd-minor-free graphs
per: Demaine, Erik D., et al.
Publicat: (2011)

Approximation algorithms via structural results for apex-minor-free graphs
per: Demaine, Erik D., et al.
Publicat: (2011)

Fixed Parameter Algorithms for Minor-Closed Graphs (of Locally Bounded Treewidth)
per: Demaine, Erik D., et al.
Publicat: (2023)

Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications
per: Demaine, Erik D., et al.
Publicat: (2023)

Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk
per: Hajiaghayi, MohammadTaghi, et al.
Publicat: (2006)

Exponential Speedup of Fixed Parameter Algorithms K_{3,3}-minor-free or K_5-minor-free Graphs
per: Demaine, Erik D., et al.
Publicat: (2023)

A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
per: Bateni, MohammadHossein, et al.
Publicat: (2018)

The bidimensionality theory and its algorithmic applications
per: Hajiaghayi, MohammadTaghi
Publicat: (2006)

Minimizing movement: Fixed-parameter tractability
per: Demaine, Erik D., et al.
Publicat: (2011)

Subexponential Parameterized Algorithms on Graphs of Bounded Genus and H-minor-free Graphs
per: Demaine, Erik D., et al.
Publicat: (2023)

Approximating Buy-at-Bulk k-Steiner trees
per: Hajiaghayi, MohammadTaghi, et al.
Publicat: (2006)

Node-weighted Steiner tree and group Steiner tree in planar graphs
per: Demaine, Erik D., et al.
Publicat: (2011)

Basic Network Creation Games
per: Alon, Noga, et al.
Publicat: (2012)

The price of anarchy in network creation games
per: Demaine, Erik D, et al.
Publicat: (2019)

Deploying Sensor Networks With Guaranteed Fault Tolerance
per: Hajiaghayi, Mohammad Taghi, et al.
Publicat: (2012)

Structural rounding: Approximation algorithms for graphs near an algorithmically tractable class
per: Demaine, Erik D, et al.
Publicat: (2020)

Scheduling to minimize gaps and power consumption
per: Demaine, Erik D., et al.
Publicat: (2014)

Information contraction and decomposition
per: Makur, Anuran.
Publicat: (2019)

How to influence people with partial incentives
per: Demaine, Erik D., et al.
Publicat: (2015)

Approximability of the Subset Sum Reconfiguration Problem
per: Ito, Takehiro, et al.
Publicat: (2014)

Low-rank approximation of parameter-dependent matrices via CUR decomposition
per: Park, T, et al.
Publicat: (2025)

A backward stable algorithm for computing the CS decomposition via the Polar decomposition
per: Gawlik, E, et al.
Publicat: (2018)

On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows
per: Hajiaghayi, MohammadTaghi, et al.
Publicat: (2005)

The Satisfiability Threshold of Random 3-SAT Is at Least 3.52
per: Hajiaghayi, MohammadTaghi, et al.
Publicat: (2005)

Tetris is Hard, Even to Approximate
per: Demaine, Erik D., et al.
Publicat: (2023)

Minimizing Movement: Fixed-Parameter Tractability
per: Demaine, Erik D, et al.
Publicat: (2022)

Minimizing Movement: Fixed-Parameter Tractability
per: Demaine, Erik D, et al.
Publicat: (2021)

O(1)-approximations for maximum movement problems
per: Berman, Piotr, et al.
Publicat: (2012)

The Facility Location Problem with Concave Cost Functions
per: Hajiaghayi, Mohammad Taghi, et al.
Publicat: (2023)

Fun with Fonts: Algorithmic Typography
per: Demaine, Erik D., et al.
Publicat: (2015)

Constant Modulus Algorithms via Low-Rank Approximation
per: Adler, Amir, et al.
Publicat: (2018)

Fun with fonts: Algorithmic typography
per: Demaine, Erik D, et al.
Publicat: (2021)

Fun with fonts: Algorithmic typography
per: Demaine, Erik D, et al.
Publicat: (2021)

Approximate inference : decomposition methods with applications to networks
per: Jung, Kyomin
Publicat: (2010)

Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
per: Demaine, Erik D, et al.
Publicat: (2021)

Interlacing families and the Hermitian spectral norm of digraphs
per: Greaves, Gary Royden Watson, et al.
Publicat: (2021)

Submodular Secretary Problem and Extensions
per: Zadimoghaddam, Morteza, et al.
Publicat: (2010)

Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
per: Borradaile, Glencora, et al.
Publicat: (2014)

Dissection with the Fewest Pieces is Hard, Even to Approximate
per: Manurangsi, Pasin, et al.
Publicat: (2018)