Approximation Algorithms via Contraction Decomposition

Approximation Algorithms via Contraction Decomposition

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

Bibliographic Details
Main Authors:	Hajiaghayi, Mohammad Taghi, Demaine, Erik D., Mohar, Bojan
Other Authors:	Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format:	Article
Language:	en_US
Published:	Bolyai Society/Springer-Verlag 2011
Online Access:	http://hdl.handle.net/1721.1/63808 https://orcid.org/0000-0003-3803-5703

Similar Items

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

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

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

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

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

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

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

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

The bidimensionality theory and its algorithmic applications
by: Hajiaghayi, MohammadTaghi
Published: (2006)

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

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

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

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

Basic Network Creation Games
by: Alon, Noga, et al.
Published: (2012)

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

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

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

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

Information contraction and decomposition
by: Makur, Anuran.
Published: (2019)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Approximate inference : decomposition methods with applications to networks
by: Jung, Kyomin
Published: (2010)

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

Submodular Secretary Problem and Extensions
by: Zadimoghaddam, Morteza, et al.
Published: (2010)

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

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