Bandwidth Sharing Network Design for Multi-class Traffic (2009)
Mohammadtaghi Hajiaghayi, Li (erran Li, Vahab S. Mirrokni, Marina Thottan
Abstract — With the increasing commercial interest in supporting voice and multimedia services over the IP network there is a need for bandwidth guaranteed services. For example, guaranteeing the...
Stochastic Steiner Tree with Non-Uniform Inflation (2009)
Anupam Gupta, Mohammadtaghi Hajiaghayi, Amit Kumar, Sloan Fellowship
Abstract. We study the Steiner Tree problem in the model of two-stage stochastic optimization with non-uniform inflation factors, and give a poly-logarithmic approximation factor for this problem. In...
The Price of Anarchy in Cooperative Network Creation Games (2009)
Demaine, Erik D., Hajiaghayi, Mohammadtaghi, Mahini, Hamid, Zadimoghaddam, Morteza
In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost \alpha. Together the agents create a network (a...
Abstract We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinalembedding, it is...
problems and computations (2009)
Mohammadhossein Bateni, Mohammadtaghi Hajiaghayi
Embedding metrics into constant-dimensional geometric spaces, such as the Euclidean plane, is relatively poorly understood. Motivated by applications in visualization, ad-hoc networks, and molecular...
The Price of Anarchy in Cooperative Network Creation Games (2009)
Demaine, Erik D., Hajiaghayi, Mohammadtaghi, Mahini, Hamid, Zadimoghaddam, Morteza
In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost α. Together the agents create a...
The Price of Anarchy in Cooperative Network Creation Games (2009)
Demaine, Erik D., Hajiaghayi, Mohammadtaghi, Mahini, Hamid, Zadimoghaddam, Morteza
In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost α. Together the agents create a...
The Price of Anarchy in Cooperative Network Creation Games (2009)
Demaine, Erik D., Hajiaghayi, MohammadTaghi, Mahini, Hamid, Zadimoghaddam, Morteza
We analyze the structure of equilibria and the price of anarchy in the family of network creation games considered extensively in the past few years, which attempt to unify the network design and...
Erik D. Demaine, Mohammadtaghi Hajiaghayi
The date of receipt and acceptance will be inserted by the editor Abstract Eppstein [5] characterized the minor-closed graph families for which the treewidth is bounded by a function of the diameter,...
Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications (2008)
Erik D. Demaine, MohammadTaghi Hajiaghayi
We solve an open problem posed by Eppstein in 1995 [14, 15] and re-enforced by Grohe [16, 17] concerning locally bounded treewidth in minor-closed families of graphs. A graph has bounded local...
ABSTRACT Low-Dimensional Embedding with Extra Information (2008)
Mihai Bădoiu, Erik D. Demaine, Mohammadtaghi Hajiaghayi, Piotr Indyk
A frequently arising problem in computational geometry is when a physical structure, such as an ad-hoc wireless sensor network or a protein backbone, can measure local information about its geometry...
Abstract Minimizing Movement (2008)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Hamid Mahini, Shayan Oveisgharan, Morteza Zadimoghaddam
We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion of a large collection of objects...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
The date of receipt and acceptance will be inserted by the editor Abstract We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on any class of graphs...
Tight Bounds For Random MAX 2-SAT (2008)
Mohammadtaghi Hajiaghayi, Jeong Han Kim
For a conjunctive normal form formula F with n variables and m = cn 2-variable clauses (c is called the density), denote by max F is the maximum number of clauses satisfiable by a single assignment...
Low-Dimensional Embedding with Extra (2008)
Mihai Bădoiu, Erik D. Demaine, Mohammadtaghi Hajiaghayi, Piotr Indyk
(will be inserted by the editor)
Scheduling to Minimize Gaps and Power Consumption ABSTRACT (2008)
Erik D. Demaine, Mohammad Ghodsi, Mohammadtaghi Hajiaghayi
This paper considers scheduling tasks while minimizing the power consumption of one or more processors, each of which can go to sleep at a fixed cost α. There are two natural versions of this...
Mohammadtaghi Hajiaghayi, F. Thomson Leighton
the max-flow min-cut ratio for directed multicommodity flows
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Hamid Mahini, Shayan Oveisgharan, Morteza Zadimoghaddam
We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion of a large collection of objects...
Abstract Combination Can Be Hard: Approximability of the Unique Coverage Problem (2008)
Mohammadtaghi Hajiaghayi, Mohammad R. Salavatipour
We prove semi-logarithmic inapproximability for a maximization problem called unique coverage: given a collection of sets, find a subcollection that maximizes the number of elements covered exactly...
problems MINIMUM LINEAR ARRANGEMENT, (2008)
Moses Charikar, Mohammadtaghi Hajiaghayi, Satish Rao
We design approximation algorithms for the vertex ordering
Erik D. Demaine, Mohammad Ghodsi, Mohammadtaghi Hajiaghayi, Morteza Zadimoghaddam
This paper considers scheduling tasks while minimizing the power consumption of one or more processors, each of which can go to sleep at a fixed cost α. There are two natural versions of this...
problems and computations (2008)
Mohammadhossein Bateni, Mohammadtaghi Hajiaghayi
Embedding metrics into constant-dimensional geometric spaces, such as the Euclidean plane, is relatively poorly understood. Motivated by applications in visualization, ad-hoc networks, and molecular...
Mohammadtaghi Hajiaghayi, Tom Leighton
the max-flow min-cut ratio for directed multicommodity flows
Mohammadtaghi Hajiaghayi, Kamal Jain
In this paper we study the prize-collecting version of the Generalized Steiner Tree problem. To the best of our knowledge, there is no general combinatorial technique in approximation algorithms...
Abstract Minimizing Movement (2008)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Hamid Mahini, Shayan Oveisgharan, Morteza Zadimoghaddam
We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion of a large collection of objects...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
The date of receipt and acceptance will be inserted by the editor Abstract We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on any class of graphs...
Approximating Buy-at-Bulk (2008)
Mohammadtaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour
and shallow-light k-Steiner trees ∗
Bandwidth Sharing Network Design for Multi-class Traffic (2008)
Mohammadtaghi Hajiaghayi, Li (erran Li, Vahab S. Mirrokni, Marina Thottan
Abstract — With the increasing commercial interest in supporting voice and multimedia services over the IP network there is a need for bandwidth guaranteed services. For example, guaranteeing the...
Stochastic Steiner Tree with Non-Uniform Inflation (2008)
Anupam Gupta, Mohammadtaghi Hajiaghayi, Amit Kumar
Abstract. We study the Steiner Tree problem in the model of two-stage stochastic optimization with non-uniform inflation factors, and give a poly-logarithmic approximation factor for this problem. In...
Abstract Semi-oblivious Routing: Lower Bounds (2008)
Mohammadtaghi Hajiaghayi, Robert Kleinberg, Tom Leighton
We initiate the study of semi-oblivious routing, a relaxation of oblivious routing which is first introduced by Räcke and led to many subsequent improvements and applications. In semi-oblivious...
Fast approximation schemes for K_{3,3}-minor-free or K_5-minor-free graphs (2008)
Mohammadtaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos
We prove that any graph excluding one of K5 or K3;3 as a minor has local treewidth bounded by 3k + 4. As a result, we can design practical polynomial-time approximation schemes for both minimization...
Avrim Blum, Mohammadtaghi Hajiaghayi, Aaron Roth, Katrina Ligett
We propose weakening the assumption made when studying the price of anarchy: Rather than assume that selfinterested players will play according to a Nash equilibrium (which may even be...
The Bidimensionality Theory and Its Algorithmic Applications (2008)
Demaine, Erik D., Hajiaghayi, MohammadTaghi
This paper surveys the theory of bidimensionality. This theory characterizes a broad range of graph problems (‘bidimensional’) that admit efficient approximate or fixed-parameter solutions in a...
excluding single-crossing graphs as minors (2007)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Prabhakar Ragde, Dimitrios M. Thilikos
algorithms for classes of graphs
Therese Biedl, Timothy Chan, Yashar Ganjali, Mohammadtaghi Hajiaghayi, David R. Wood
We consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbors of each vertex v are as evenly distributed to the left and right of v as possible. This...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos
graphs as minors
Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammadtaghi Hajiaghayi
y, Tomas Vinar
Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammadtaghi Hajiaghayi
y, Tomas Vinar
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. We present a fixed parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of the K5 or K3;3 as a minor in time O(3 6
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. We present a xed parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of the K5 or K3;3 as a minor in time O(3 6
Therese Biedl, Timothy Chan, Yashar Ganjali, Mohammadtaghi Hajiaghayi, David R. Wood
We consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbors of each vertex v are as evenly distributed to the left and right of v as possible. This...
Clustering algorithms in PBS (2007)
A software system is typically comprised of several interconnected components, such as procedures, functions, etc. The software re-engineering attempts to deal with the difficult problems of...
Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs (2007)
Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos
The (k, r)-center problem asks whether an input graph G has k vertices (called centers) such that every vertex of G is within distance r from some center. In this paper we prove that the (k,...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos
graphs as minors
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
For several graph theoretic parameters such as vertex cover and dominating set, it is known that if their values are bounded by k then the treewidth of the graph is bounded by some function of k....
Erik D. Demaine, Mohammadtaghi Hajiaghayi
The date of receipt and acceptance will be inserted by the editor Abstract Eppstein [5] characterized the minor-closed graph families for which the treewidth is bounded by a function of the diameter,...
Subgraph Isomorphism, log-Bounded Fragmentation, and Graphs of (Locally) Bounded Treewidth (2007)
Mohammadtaghi Hajiaghayi, Naomi Nishimura
The subgraph isomorphism problem, that of nding a copy of one graph in another, has proved to be intractable except when certain restrictions are placed on the inputs. In this paper, we introduce a...
Dial a Ride from k-forest (2007)
Gupta, Anupam, Hajiaghayi, MohammadTaghi, Nagarajan, Viswanath, Ravi, R.
The k-forest problem is a common generalization of both the k-MST and the dense-$k$-subgraph problems. Formally, given a metric space on $n$ vertices $V$, with $m$ demand pairs $\subseteq V \times V$...
Approximation algorithms via contraction decomposition (2007)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Bojan Mohar
We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth...
Regret minimization and the price of total anarchy (2007)
Avrim Blum, Mohammadtaghi Hajiaghayi, Katrina Ligett, Aaron Roth
We propose weakening the assumption made when studying the price of anarchy: Rather than assume that self-interested players will play according to a Nash equilibrium (which may even be...
Regret minimization and the price of total anarchy (2007)
Avrim Blum, Mohammadtaghi Hajiaghayi, Katrina Ligett, Aaron Roth
We propose weakening the assumption made when studying the price of anarchy: Rather than assume that self-interested players will play according to a Nash equilibrium (which may even be...
Dial a ride from k-Forest (2007)
Anupam Gupta, Mohammadtaghi Hajiaghayi, Viswanath Nagarajan, R. Ravi
The k-forest problem is a common generalization of both the k-MST and the dense-k-subgraph problems. Formally, given a metric space on n vertices V, with m demand pairs ⊆ V × V and a “target ”...
Automated online mechanism design and prophet inequalities (2007)
Recent work on online auctions for digital goods has explored the role of optimal stopping theory — particularly secretary problems — in the design of approximately optimal online mechanisms....
HAJIAGHAYI: A theory of loss-leaders: Making money by pricing below cost (2007)
Maria-florina Balcan, Avrim Blum, Mohammadtaghi Hajiaghayi
Abstract. We consider the problem of assigning prices to goods of fixed marginal cost in order to maximize revenue in the presence of singleminded customers. We focus in particular on the question of...
Approximation algorithms via contraction decomposition (2007)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Bojan Mohar
We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth...
Dial a ride from k-Forest (2007)
Anupam Gupta, Mohammadtaghi Hajiaghayi, Viswanath Nagarajan, R. Ravi
The k-forest problem is a common generalization of both the k-MST and the dense-k-subgraph problems. Formally, given a metric space on n vertices V, with m demand pairs ⊆ V × V and a “target ”...
Regret minimization and the price of total anarchy (2007)
Avrim Blum, Mohammadtaghi Hajiaghayi, Aaron Roth, Katrina Ligett
We propose weakening the assumption made when studying the price of anarchy: Rather than assume that selfinterested players will play according to a Nash equilibrium (which may even be...
Algorithmic graph minor theory: Improved grid minor bounds and wagner’s contraction (2006)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Ken-ichi Kawarabayashi
Algorithmic graph minor theory: Improved grid minor bounds and wagner’s contraction (2006)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Ken-ichi Kawarabayashi
We explore three important avenues of research in algorithmic graph-minor theory, which all stem from a key min-max relation between the treewidth of a graph and its largest grid minor. This min-max...
Combination Can Be Hard: Approximability of the Unique Coverage Problem (2006)
Erik D. Demaine, Uriel Feige, Mohammadtaghi Hajiaghayi, Mohammad R. Salavatipour
Abstract We prove semi-logarithmic inapproximability for a maximization problem called unique coverage:given a collection of sets, find a subcollection that maximizes the number of elements covered...
Algorithmic graph minor theory: Improved grid minor bounds and wagner’s contraction (2006)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Ken-ichi Kawarabayashi
Abstract We explore three important avenues of research in algorithmic graph-minor theory, whichall stem from a key min-max relation between the treewidth of a graph and its largest grid
Approximating Buy-at-Bulk and Shallow-light k-Steiner trees (2006)
Mohammadtaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour
Abstract We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V, E) with a set of terminals T ` V including...
Approximating Buy-at-Bulk and Shallow-light k-Steiner trees (2006)
Mohammadtaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour
Abstract We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V, E) with a set of terminals T ` V including...
An O( √ n)-Approximation Algorithm For Directed Sparsest (2006)
Mohammadtaghi Hajiaghayi, Harald Räcke
We give an O ( √ n)-approximation algorithm for the Sparsest Cut Problem on directed graphs. A naïve reduction from Sparsest Cut to Minimum Multicut would only give an approximation ratio of O (...
Algorithmic graph minor theory: Improved grid minor bounds and wagner’s contraction (2006)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Ken-ichi Kawarabayashi
Abstract. We explore the three main avenues of research still unsolved in the algorithmic graph-minor theory literature, which all stem from a key min-max relation between the treewidth of a graph...
Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk (2005)
Hajiaghayi, MohammadTaghi, Kortsarz, Guy, Salavatipour, Mohammad R.
We consider the non-uniform multicommodity buy-at-bulknetworkdesign problem. In this problem we are given a graph $G(V,E)$withtwo cost functions on the edges, a buy cost $b:E\longrightarrow \RR^+$and...
Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk (2005)
Hajiaghayi, MohammadTaghi, Kortsarz, Guy, Salavatipour, Mohammad R.
We consider the non-uniform multicommodity buy-at-bulknetworkdesign problem. In this problem we are given a graph $G(V,E)$withtwo cost functions on the edges, a buy cost $b:E\longrightarrow \RR^+$and...
Approximating Buy-at-Bulk k-Steiner trees (2005)
Hajiaghayi, MohammadTaghi, Kortsarz, Guy, Salavatipour, Mohammad R.
In the buy-at-bulk $k$-Steiner tree (or rent-or-buy$k$-Steiner tree) problem we are given a graph $G(V,E)$ with a setof terminals $T\subseteq V$ including a particular vertex $s$ calledthe root, and...
Approximating Buy-at-Bulk k-Steiner trees (2005)
Hajiaghayi, MohammadTaghi, Kortsarz, Guy, Salavatipour, Mohammad R.
In the buy-at-bulk $k$-Steiner tree (or rent-or-buy$k$-Steiner tree) problem we are given a graph $G(V,E)$ with a setof terminals $T\subseteq V$ including a particular vertex $s$ calledthe root, and...
Bidimensionality, Map Graphs, and Grid Minors (2005)
Demaine, Erik D., Hajiaghayi, MohammadTaghi
In this paper we extend the theory of bidimensionality to two families of graphs that do not exclude fixed minors: map graphs and power graphs. In both cases we prove a polynomial relation between...
The bidimensionality theory and its algorithmic applications (2005)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005.
The bidimensionality theory and its algorithmic applications (2005)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005.
The bidimensionality theory and its algorithmic applications / (2005)
Our newly developing theory of bidimensional graph problems provides general techniques for designing efficient fixed-parameter algorithms and approximation algorithms for NP- hard graph problems in...
The bidimensionality Theory and Its Algorithmic Applications (2005)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
This paper surveys the theory of bidimensionality. This theory characterizes a broad range of graph problems (‘bidimensional’) that admit efficient approximate or fixed-parameter solutions in a...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of K5 or K3;3 as a minor in time O(416:5 pk nO(1)), which is an...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimumrelaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimumrelaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Oblivious routing in directed graphs with random demands (2005)
Mohammadtaghi Hajiaghayi, Jeong Han, Kim Tom, Leighton Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. More precisely, Räcke showed that...
The bidimensionality Theory and Its Algorithmic Applications (2005)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
doi:10.1093/comjnl/bxh000
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimumrelaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Oblivious routing in directed graphs with random demands (2005)
Mohammadtaghi Hajiaghayi, Jeong Han, Kim Tom, Leighton Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. More precisely, Räcke showed that...
Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring (2005)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Ken-ichi Kawarabayashi
At the core of the seminal Graph Minor Theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph...
Deploying sensor networks with guaranteed capacity and fault tolerance (2005)
Jonathan L. Bredin, Erik D. Demaine, Mohammadtaghi Hajiaghayi, Daniela Rus
We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multi-path connectivity (k-connectivity) between all nodes. Such a guarantee simultaneously...
Oblivious routing on node-capacitated and directed graphs (2005)
Mohammadtaghi Hajiaghayi, Robert D. Kleinberg, Harald Räcke, Tom Leighton
Oblivious routing algorithms for general undirected networks were introduced by Räcke [Räcke 2002], and this work has led to many subsequent improvements and applications. Comparatively little is...
The Bidimensionality Theory (2005)
Mohammadtaghi Hajiaghayi, Erik D. Demaine, Mohammadtaghi Hajiaghayi
newly developing theory of bidimensional graph problems provides general techniques for designing efficient fixed-parameter algorithms and approximation algorithms for NPhard graph problems in broad...
Mohammadtaghi Hajiaghayi, Advisors Erik, D. Demaine, Tom Leighton, Naomi Nishimura, Summer Students
Email is the fastest and the most reliable way of contacting me.
Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth (2004)
Demaine, Erik D., Hajiaghayi, MohammadTaghi
This paper surveys the theory of bidimensional graph problems. We summarize the known combinatorial and algorithmic results of this theory, the foundational Graph Minor results on which this theory...
Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth (2004)
Demaine, Erik D., Hajiaghayi, MohammadTaghi
This paper surveys the theory of bidimensional graph problems. We summarize the known combinatorial and algorithmic results of this theory, the foundational Graph Minor results on which this theory...
Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth (2004)
Demaine, Erik D., Hajiaghayi, MohammadTaghi
This paper surveys the theory of bidimensional graph problems. We summarize the known combinatorial and algorithmic results of this theory, the foundational Graph Minor results on which this theory...
Equivalence of local treewidth and linear local treewidth and its algorithmic applications (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
We solve an open problem posed by Eppstein in 1995 [14, 15] and re-enforced by Grohe [16, 17] concerning locally bounded treewidth in minor-closed families of graphs. A graph has bounded local...
Bidimensional parameters and local treewidth (2004)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. For several graph theoretic parameters such as vertex cover and dominating set, it is known that if their values are bounded by k then the treewidth of the graph is bounded by some function...
Bidimensional parameters and local treewidth (2004)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by k then the treewidth of the graph is bounded by some function...
Low-dimensional embedding with extra information (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Piotr Indyk
ABSTRACT A frequently arising problem in computational geometry is whena physical structure, such as an ad-hoc wireless sensor network or
Fast algorithms for hard graph problems: Bidimensionality, minors, and local treewidth (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
Abstract. This paper surveys the theory of bidimensional graph problems. We summarize the known combinatorial and algorithmic results of this theory, the foundational Graph Minor results on which...
Quickly deciding minor-closed parameters in general graphs (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
We construct algorithms for deciding essentially any minor-closed parameter, with explicit time bounds. This result strengthens previous results by Robertson and Seymour [1,2], Frick and Grohe [3],...
The bidimensional theory of bounded-genus graphs (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
1 Introduction The recent theory of fixed-parameter algorithms and parameterized complex-ity [13] has attracted much attention in its less than 10 years of existence. In general the goal is to...
The bidimensional theory of bounded-genus graphs (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. Bidimensionality provides a tool for developing subexponential fixed-parameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper extends...
Bidimensional parameters and local treewidth (2004)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Equivalence of local treewidth and linear local treewidth and its algorithmic applications (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
Abstract. We solve an open problem posed by Eppstein in 1995 [16, 17] and re-enforced by Grohe [18, 19] concerning locally bounded treewidth in minor-closed families of graphs. A graph has bounded...
The bidimensional theory of bounded-genus graphs (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. Bidimensionality is a powerful tool for developing subexponential fixedparameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper...
Balanced Vertex-Orderings of Graphs (2004)
Therese Biedl, Timothy Chan, Yashar Ganjali, Mohammadtaghi Hajiaghayi, David R. Wood
In this paper we consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbors of each vertex v are as evenly distributed to the left and right of v as...
Bidimensional Parameters and Local Treewidth (2004)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by k then the treewidth of the graph is bounded by some function of k. This...
Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs (2004)
Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos
We introduce a new framework for designing xed-parameter algorithms with subexponential running time|2 . Our results apply to a broad family of graph problems, called bidimensional problems, which...
The bidimensional theory of bounded-genus graphs (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. Bidimensionality provides a tool for developing subexponential fixed-parameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper extends...
Low-dimensional embedding with extra information (2004)
Mihai Bădoiu, Erik D. Demaine, Mohammadtaghi Hajiaghayi, Piotr Indyk
A frequently arising problem in computational geometry is when a physical structure, such as an ad-hoc wireless sensor network or a protein backbone, can measure local information about its geometry...
Quickly deciding minor-closed parameters in general graphs (2004)
Erik D. Demaine, Mohammadtaghi Hajiaghayi
We construct algorithms for deciding essentially any minor-closed parameter, with explicit time bounds. This result strengthens previous results by Robertson and Seymour [1,2], Frick and Grohe [3],...
Bidimensional parameters and local treewidth (2004)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, M. Thilikos, Dimitrios M. Thilikos
For several graph theoretic parameters such as vertex cover and dominating set, it is known that if their values are bounded by k then the treewidth of the graph is bounded by some function of k....
Low-Dimensional Embedding with Extra Information (2004)
Mihai Badoiu, Erik D. Demaine, Mohammadtaghi Hajiaghayi, Piotr Indyk
A frequently arising problem in computational geometry is when a physical structure, such as an ad-hoc wireless sensor network or a protein backbone, can measure local information about its geometry...
The Satisfiability Threshold of Random 3-SAT Is at Least 3.52 (2003)
Hajiaghayi, MohammadTaghi, Sorkin, Gregory B.
We prove that a random 3-SAT instance with clause-to-variable densityless than 3.52 is satisfiable with high probability.The proof comes through an algorithm which selects (and sets) a...
The Satisfiability Threshold of Random 3-SAT Is at Least 3.52 (2003)
Hajiaghayi, MohammadTaghi, Sorkin, Gregory B.
We prove that a random 3-SAT instance with clause-to-variable densityless than 3.52 is satisfiable with high probability.The proof comes through an algorithm which selects (and sets) a...
The Satisfiability Threshold of Random 3-SAT Is at Least 3.52 (2003)
Hajiaghayi, MohammadTaghi, Sorkin, Gregory B.
We prove that a random 3-SAT instance with clause-to-variable density less than 3.52 is satisfiable with high probability. The proof comes through an algorithm which selects (and sets) a variable...
On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows (2003)
Hajiaghayi, MohammadTaghi, Leighton, F. Thomson
We give a pure combinatorial problem whose solution determines max-flow min-cut ratio for directed multicommodity flows. In addition, this combinatorial problem has applications in improving the...
On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows (2003)
Hajiaghayi, MohammadTaghi, Leighton, F. Thomson
We give a pure combinatorial problem whose solution determines max-flow min-cut ratio for directed multicommodity flows. In addition, this combinatorial problem has applications in improving the...
Thilikos, Fixed-parameter algorithms for the (k, r)-center in planar graphs and map graphs (2003)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs (2003)
Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos
The (k, r)-center problem asks whether an input graph G has k vertices (called centers) such that every vertex of G is within distance r from some center. In this paper we prove that the (k,...
Mohammadtaghi Hajiaghayi, Nicole Immorlica, Vahab S. Mirrokni
In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power while...
Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs (2003)
Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos
The facility location problem with general cost functions (2003)
Mohammadtaghi Hajiaghayi, Mohammad Mahdian, Vahab S. Mirrokni
Abstract. In this paper we dene and study a generalized version of the facility location problem in which facility costs depend on the number of clients assigned to the facility. There is an...
The Satisfiability Threshold of Random 3-SAT Is at Least 3.52 (2003)
Mohammadtaghi Hajiaghayi, Gregory B. Sorkin
We prove that a random 3-SAT instance with clause-to-variable density less than 3.52 is satis able with high probability. The proof comes through an algorithm which selects (and sets) a variable...
On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows (2003)
Mohammadtaghi Hajiaghayi, F. Thomson Leighton
We give a pure combinatorial problem whose solution determines max-flow min-cut ratio for directed multicommodity flows. In addition, this combinatorial problem has applications in improving the...
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs
The satisfiability threshold for random 3-SAT is at least 3.52 (2003)
Mohammadtaghi Hajiaghayi, Mohammadtaghi Hajiaghayi, Gregory B. Sorkin, Gregory B. Sorkin
been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be...
Fixed-parameter algorithms for the (k, r)-center in planar graphs and map graphs (2003)
Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos
The (k; r)-center problem asks whether an input graph G has k vertices (called centers) such that every vertex of G is within distance r from some center. In this paper we prove that the (k;...
Thilikos, Fixed-parameter algorithms for the (k, r)-center in planar graphs and map graphs (2003)
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. The (k, r)-center problem asks whether an input graph G has ≤ k vertices (called centers) such that every vertex of G is within distance ≤ r from some center. In this paper we prove...
Power Optimization in Fault-Tolerant Topology Control Algorithms for (2003)
Mohammadtaghi Hajiaghayi, Nicole Immorlica
ABSTRACT In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power...
A 1.5-approximation for treewidth of graphs excluding a graph with one crossing (2002)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The...
A 1.5-approximation for treewidth of graphs excluding a graph with one crossing (2002)
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on any class of graphs excluding a single-crossing graph (a graph that can be drawn in the plane with at...
Facility location problem with concave cost functions. unpublished manuscript (2002)
Mohammadtaghi Hajiaghayi, Mohammad Mahdian, Vahab S. Mirrokni
Abstract. In this paper we dene and study a generalized version of facility location problem in which facility cost functions depend on the number of clients assigned to the facility. There is an...
Facility location problem with concave cost functions. unpublished manuscript (2002)
Mohammadtaghi Hajiaghayi, Mohammad Mahdian, Vahab S. Mirrokni
Abstract. In this paper we define and study a generalized version of facility location problem in which facility cost functions depend on the number of clients assigned to the facility. There is an...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
We present a fixed parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of the K5 or K3,3 as a minor in time O(3 6 √ 34k n O(1)). In fact, we present...
Subgraph isomorphism, log-bounded fragmentation and graphs of (locally) bounded treewidth (2002)
Mohammadtaghi Hajiaghayi, Naomi Nishimura
Abstract. The subgraph isomorphism problem, that of nding a copy of one graph in another, has proved to be intractable except when certain restrictions are placed on the inputs. In this paper, we...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. We present a fixed parameter algorithm that constructively solves the k-dominating set prob-lem on graphs excluding one of K5 or K3,3 as a minor in time O(36n()), which is an exponential...
Subgraph isomorphism, log-bounded fragmentation and graphs of (locally) bounded treewidth (2002)
Abstract. Matouek and Thomas solved the subgraph isomorphism problem when the source graph has bounded degree and the host graph has bounded treewidth. In this paper, we introduce a new property for...
A note on the consecutive ones submatrix problem (2002)
Mohammadtaghi Hajiaghayi, Yashar Ganjali
A binary matrix has the Consecutive Ones Property (C1P) for columns if there exists a permutation of its rows that leaves the 1's consecutive in every column. The problem of Consecutive Ones...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
We present a fixed parameter algorithm that constructively solves the k-dominating set problem on any class of graphs excluding a single-crossing graph (can be drawn on the plane with at most one...
Subgraph isomorphism, log-bounded fragmentation and graphs of (locally) bounded treewidth (2002)
Mohammadtaghi Hajiaghayi, Naomi Nishimura
1 Introduction In this paper we consider the subgraph isomorphism problem, in which we search for a subgraph of host graph H isomorphic to the source (or pattern) graph G. This problem arises in...
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Abstract. We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of K5 or K3,3 as a minor in time O(4 16.5 √ k n O(1)), which is an...
Characterization of Networks Supporting Multi-dimensional Linear Interval Routing Schemes (2001)
Yashar Ganjali, Mohammadtaghi Hajiaghayi
An Interval Routing Scheme (IRS) is a well-known, space ecient routing strategy for routing messages in a distributed network. In this scheme, each node of the network is assigned an integer label...
Balanced vertex-orderings of graphs (2001)
Therese Biedl, Timothy Chan, Mohammadtaghi Hajiaghayi, Yashar Ganjali
In this paper we consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbouts of each vertex v are as evenly distributed to the left and right of v as...
Characterization of Networks Supporting Multi-dimensional Linear Interval Routing Schemes (2001)
An Interval Routing Scheme (IRS) is a well-known, space efficient routing strategy for routing messages in a distributed network. In this scheme, each node of the network is assigned an integer label...
Comparing of SGML documents (2001)
Documents can be represented as structures with a hierarchial arrangement of text and non-text nodes, where nodes are labeled by category names such as paragraph and section. Representing documents...
Algorithms for Graphs of (Locally) Bounded Treewidth (2001)
I hereby declare that I am the sole author of this thesis. I authorize the University of Waterloo to lend this thesis to other institutions or individuals for the purpose of scholarly research.
Balanced vertex-orderings of graphs (2001)
Therese Biedl, Timothy Chan, Yashar Ganjali, Mohammadtaghi Hajiaghayi, David R. Wood
In this paper we consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbours of each vertex v are as evenly distributed to the left and right of v as...
Consecutive ones property (2000)
A binary matrix has the Consecutive Ones Property(C1P) for columns if there is a permutation of its rows that leaves the 1's consecutive in every column. We study some results and algorithms...
The Bidimensional Theory of Bounded-Genus Graphs
Erik D. Demaine, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
Bidimensionality is a powerful tool for developing subexponential fixed-parameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper completes the...