| Publication | Date of Publication | Type |
|---|
Distributed fractional local ratio and independent set approximation
Information and Computation | 2025-02-28 | Paper |
| A distributed palette sparsification theorem | 2024-11-28 | Paper |
Online multiset submodular cover
Algorithmica | 2024-08-02 | Paper |
| Fast distributed Brooks' theorem | 2024-05-14 | Paper |
Overcoming Congestion in Distributed Coloring
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Distributed coloring of hypergraphs
Structural Information and Communication Complexity | 2024-01-11 | Paper |
Near-optimal distributed degree+1 coloring
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Efficient randomized distributed coloring in CONGEST
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
| Coloring fast without learning your neighbors' colors | 2023-11-02 | Paper |
| Greedy approximations of independent sets in low degree graphs | 2023-03-21 | Paper |
Superfast coloring in CONGEST via efficient color sampling
Theoretical Computer Science | 2023-02-13 | Paper |
| An efficient communication abstraction for dense wireless networks | 2023-02-03 | Paper |
| Approximation and special cases of common subtrees and editing distance | 2023-01-25 | Paper |
Approximations for the general block distribution of a matrix
Algorithm Theory — SWAT'98 | 2022-12-09 | Paper |
Facility dispersion and remote subgraphs
Algorithm Theory — SWAT'96 | 2022-12-09 | Paper |
Improved approximations of independent sets in bounded-degree graphs
Algorithm Theory — SWAT '94 | 2022-12-09 | Paper |
Approximating maximum independent sets by excluding subgraphs
SWAT 90 | 2022-12-09 | Paper |
Query minimization under stochastic uncertainty
LATIN 2020: Theoretical Informatics | 2022-10-13 | Paper |
Distributed Testing of Distance-k Colorings
Structural Information and Communication Complexity | 2022-09-01 | Paper |
| Query-Competitive Sorting with Uncertainty. | 2022-07-21 | Paper |
| Generalized disk graphs | 2022-03-25 | Paper |
Tight bounds on subexponential time approximation of set cover and related problems
(available as arXiv preprint) | 2022-03-22 | Paper |
Superfast coloring in CONGEST via efficient color sampling
Structural Information and Communication Complexity | 2022-03-22 | Paper |
Posimodular function optimization
Algorithmica | 2022-03-22 | Paper |
| Wireless network algorithmics | 2022-02-16 | Paper |
Sparse Backbone and Optimal Distributed SINR Algorithms
ACM Transactions on Algorithms | 2022-02-16 | Paper |
Network design under general wireless interference
Algorithmica | 2021-11-19 | Paper |
Query minimization under stochastic uncertainty
Theoretical Computer Science | 2021-11-18 | Paper |
Query minimization under stochastic uncertainty
Theoretical Computer Science | 2021-11-18 | Paper |
Computing inductive vertex orderings
Information Processing Letters | 2021-10-19 | Paper |
Spanning trees with edge conflicts and wireless connectivity
(available as arXiv preprint) | 2021-07-28 | Paper |
Query-competitive sorting with uncertainty
Theoretical Computer Science | 2021-04-15 | Paper |
Query-competitive sorting with uncertainty
Theoretical Computer Science | 2021-04-15 | Paper |
Effective Wireless Scheduling via Hypergraph Sketches
SIAM Journal on Computing | 2021-04-14 | Paper |
Local improvement algorithms for a path packing problem: a performance analysis based on linear programming
Operations Research Letters | 2021-04-07 | Paper |
Distance-2 Coloring in the CONGEST Model
Proceedings of the 39th Symposium on Principles of Distributed Computing | 2021-03-15 | Paper |
Plain SINR is Enough!
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | 2021-01-20 | Paper |
Distributed Minimum Degree Spanning Trees
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | 2021-01-20 | Paper |
Simple and local independent set approximation
Theoretical Computer Science | 2020-11-06 | Paper |
Radio aggregation scheduling
Theoretical Computer Science | 2020-09-17 | Paper |
Limitations of current wireless link scheduling algorithms
Theoretical Computer Science | 2020-09-17 | Paper |
Universal framework for wireless scheduling problems
(available as arXiv preprint) | 2020-05-27 | Paper |
Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
Theoretical Computer Science | 2020-02-13 | Paper |
Leader election in SINR model with arbitrary power control
Theoretical Computer Science | 2020-02-13 | Paper |
Leveraging Indirect Signaling for Topology Inference and Fast Broadcast
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
Brief announcement: Simple and local independent set approximation
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
Leveraging multiple channels in ad hoc networks
Distributed Computing | 2019-06-20 | Paper |
The power of non-uniform wireless power
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Wireless connectivity and capacity
(available as arXiv preprint) | 2019-05-10 | Paper |
| Wireless connectivity and capacity | 2019-05-10 | Paper |
Distributed approximation of k-service assignment
Distributed Computing | 2019-03-21 | Paper |
Simple and local independent set approximation
Structural Information and Communication Complexity | 2019-01-30 | Paper |
Approximating \(k\)-set cover and complementary graph coloring
Integer Programming and Combinatorial Optimization | 2019-01-11 | Paper |
Improved bounds for scheduling conflicting jobs with minsum criteria
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Space-constrained interval selection
ACM Transactions on Algorithms | 2018-11-05 | Paper |
| Distributed large independent sets in one round on bounded-independence graphs | 2018-08-24 | Paper |
Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
Structural Information and Communication Complexity | 2018-04-12 | Paper |
Leader election in SINR model with arbitrary power control
Structural Information and Communication Complexity | 2018-04-12 | Paper |
Distributed backup placement in networks
Distributed Computing | 2018-04-11 | Paper |
Computing large independent sets in a single round
Distributed Computing | 2018-02-23 | Paper |
Brief announcement: Leader election in SINR model with arbitrary power control
Proceedings of the ACM Symposium on Principles of Distributed Computing | 2017-10-11 | Paper |
| Wireless capacity with oblivious power in general metrics | 2017-09-29 | Paper |
Wireless capacity with oblivious power in general metrics
(available as arXiv preprint) | 2017-09-29 | Paper |
| Distributed approximation of \(k\)-service assignment | 2017-09-29 | Paper |
Brief Announcement
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing | 2017-09-29 | Paper |
Brief announcement: Data dissemination in unified dynamic wireless networks
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing | 2017-09-29 | Paper |
Posimodular function optimization
Lecture Notes in Computer Science | 2017-09-22 | Paper |
The price of local power control in wireless scheduling
(available as arXiv preprint) | 2017-07-13 | Paper |
The power of oblivious wireless power
SIAM Journal on Computing | 2017-06-28 | Paper |
The minimum vulnerability problem on specific graph classes
Journal of Combinatorial Optimization | 2016-11-29 | Paper |
Max point-tolerance graphs
Discrete Applied Mathematics | 2016-11-24 | Paper |
Streaming algorithms for independent sets in sparse hypergraphs
Algorithmica | 2016-10-21 | Paper |
Greed is good: approximating independent sets in sparse and bounded-degree graphs
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Shrinking maxima, decreasing costs: new online packing and covering problems
Algorithmica | 2016-05-31 | Paper |
Nearly optimal bounds for distributed wireless scheduling in the SINR model
Distributed Computing | 2016-05-23 | Paper |
A local broadcast layer for the SINR network model
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing | 2016-03-23 | Paper |
Leveraging multiple channels in ad hoc networks
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing | 2016-03-23 | Paper |
Semi-transitive orientations and word-representable graphs
Discrete Applied Mathematics | 2016-02-04 | Paper |
On the complexity of the shortest-path broadcast problem
Discrete Applied Mathematics | 2015-12-10 | Paper |
The minimum vulnerability problem on graphs
Combinatorial Optimization and Applications | 2015-09-11 | Paper |
Beyond geometry: towards fully realistic wireless models
Proceedings of the 2014 ACM symposium on Principles of distributed computing | 2015-09-03 | Paper |
Improved results for data migration and open shop scheduling
ACM Transactions on Algorithms | 2015-09-02 | Paper |
How well can graphs represent wireless interference?
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
On the Impact of Identifiers on Local Decision
Lecture Notes in Computer Science | 2015-08-05 | Paper |
On colorings of squares of outerplanar graphs
(available as arXiv preprint) | 2015-08-03 | Paper |
On spectrum sharing games
Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing | 2015-08-03 | Paper |
Vertex coloring edge-weighted digraphs
Information Processing Letters | 2015-06-15 | Paper |
Mod-2 independence and domination in graphs
International Journal of Foundations of Computer Science | 2015-04-29 | Paper |
Connectivity and aggregation in multihop wireless networks
Proceedings of the 2013 ACM symposium on Principles of distributed computing | 2015-03-02 | Paper |
Online set packing and competitive scheduling of multi-part tasks
Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing | 2015-03-02 | Paper |
Progress (and lack thereof) for graph coloring approximation problems
Lecture Notes in Computer Science | 2015-02-20 | Paper |
Distributed algorithms for coloring interval graphs
Lecture Notes in Computer Science | 2015-02-10 | Paper |
Distributed connectivity of wireless networks
Proceedings of the 2012 ACM symposium on Principles of distributed computing | 2014-12-05 | Paper |
Brief announcement
Proceedings of the 2012 ACM symposium on Principles of distributed computing | 2014-12-05 | Paper |
Wireless scheduling with power control
ACM Transactions on Algorithms | 2014-12-05 | Paper |
Corrigendum: ``Improved results for data migration and open shop scheduling''
ACM Transactions on Algorithms | 2014-12-05 | Paper |
Approximating the domatic number
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Wireless capacity with arbitrary gain matrix
Theoretical Computer Science | 2014-09-18 | Paper |
Sum edge coloring of multigraphs via configuration LP
ACM Transactions on Algorithms | 2014-09-09 | Paper |
Online selection of intervals and t-intervals
Information and Computation | 2014-01-10 | Paper |
Online scheduling with interval conflicts
Theory of Computing Systems | 2013-10-21 | Paper |
Shrinking maxima, decreasing costs: new online packing and covering problems
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
Space-constrained interval selection
Automata, Languages, and Programming | 2013-08-12 | Paper |
Streaming and communication complexity of clique approximation
Automata, Languages, and Programming | 2013-08-12 | Paper |
On spectrum sharing games
Distributed Computing | 2013-06-28 | Paper |
SDP-based algorithms for maximum independent set problems on hypergraphs
Theoretical Computer Science | 2013-02-19 | Paper |
Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees
Theoretical Computer Science | 2013-02-19 | Paper |
Online set packing
SIAM Journal on Computing | 2012-11-29 | Paper |
| Online scheduling with interval conflicts | 2012-01-23 | Paper |
Online coloring of hypergraphs
Information Processing Letters | 2012-01-18 | Paper |
Alternation graphs
Graph-Theoretic Concepts in Computer Science | 2011-12-16 | Paper |
Nearly optimal bounds for distributed wireless scheduling in the SINR model
Lecture Notes in Computer Science | 2011-07-07 | Paper |
Vertex coloring the square of outerplanar graphs of low degree
Discussiones Mathematicae Graph Theory | 2011-05-09 | Paper |
Randomized approximation of the stable marriage problem
Lecture Notes in Computer Science | 2011-03-18 | Paper |
Streaming Algorithms for Independent Sets
Automata, Languages and Programming | 2010-09-07 | Paper |
Graphs Capturing Alternations in Words
Developments in Language Theory | 2010-08-31 | Paper |
Improved approximation results for the stable marriage problem
ACM Transactions on Algorithms | 2010-08-14 | Paper |
| scientific article; zbMATH DE number 5764868 (Why is no real title available?) | 2010-08-06 | Paper |
Online selection of intervals and \(t\)-intervals
Lecture Notes in Computer Science | 2010-06-22 | Paper |
Improved approximation of the stable marriage problem
Lecture Notes in Computer Science | 2010-03-03 | Paper |
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
Information Processing Letters | 2009-12-04 | Paper |
Wireless Scheduling with Power Control
Lecture Notes in Computer Science | 2009-10-29 | Paper |
Weighted sum coloring in batch scheduling of conflicting jobs
Algorithmica | 2009-10-23 | Paper |
Scheduling with conflicts: Online and offline algorithms
Journal of Scheduling | 2009-09-25 | Paper |
Wireless Communication Is in APX
Automata, Languages and Programming | 2009-07-14 | Paper |
SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs
Automata, Languages and Programming | 2009-07-14 | Paper |
Approximation algorithms for the weighted independent set problem in sparse graphs
Discrete Applied Mathematics | 2009-06-30 | Paper |
Independent sets in bounded-degree hypergraphs
Discrete Applied Mathematics | 2009-06-24 | Paper |
Fixed-Parameter Tractability for Non-Crossing Spanning Trees
Lecture Notes in Computer Science | 2009-02-17 | Paper |
Independent Sets in Bounded-Degree Hypergraphs
Lecture Notes in Computer Science | 2009-02-17 | Paper |
Complete partitions of graphs
Combinatorica | 2008-10-21 | Paper |
| On representable graphs, semi-transitive orientations, and the representation numbers | 2008-10-01 | Paper |
Vertex coloring acyclic digraphs and their corresponding hypergraphs
Discrete Applied Mathematics | 2008-09-10 | Paper |
Strip Graphs: Recognition and Scheduling
Graph-Theoretic Concepts in Computer Science | 2008-09-04 | Paper |
Minimizing interference of a wireless ad-hoc network in a plane
Theoretical Computer Science | 2008-08-14 | Paper |
Batch Coloring Flat Graphs and Thin
Algorithm Theory – SWAT 2008 | 2008-07-15 | Paper |
Min Sum Edge Coloring in Multigraphs Via Configuration LP
Integer Programming and Combinatorial Optimization | 2008-06-10 | Paper |
“Rent-or-Buy” Scheduling and Cost Coloring Problems
FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science | 2008-04-24 | Paper |
Strongly simplicial vertices of powers of trees
Discrete Mathematics | 2007-10-25 | Paper |
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
Graph-Theoretic Concepts in Computer Science
Lecture Notes in Computer Science | 2006-11-01 | Paper |
Scheduling Split Intervals
SIAM Journal on Computing | 2006-06-01 | Paper |
Approximation and Online Algorithms
Lecture Notes in Computer Science | 2005-12-14 | Paper |
Approximation and Online Algorithms
Lecture Notes in Computer Science | 2005-12-14 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
Mathematical Foundations of Computer Science 2004
Lecture Notes in Computer Science | 2005-08-22 | Paper |
| scientific article; zbMATH DE number 2119734 (Why is no real title available?) | 2004-11-29 | Paper |
Randomized approximation of the stable marriage problem
Theoretical Computer Science | 2004-10-27 | Paper |
Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
Algorithmica | 2004-09-22 | Paper |
| scientific article; zbMATH DE number 2089217 (Why is no real title available?) | 2004-08-12 | Paper |
| scientific article; zbMATH DE number 2086256 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2080247 (Why is no real title available?) | 2004-08-04 | Paper |
Approximability results for stable marriage problems with ties.
Theoretical Computer Science | 2004-03-14 | Paper |
Approximation algorithms for the test cover problem
Mathematical Programming. Series A. Series B | 2004-03-11 | Paper |
Coloring Powers of Planar Graphs
SIAM Journal on Discrete Mathematics | 2004-01-08 | Paper |
Powers of geometric intersection graphs and dispersion algorithms
Discrete Applied Mathematics | 2003-12-04 | Paper |
Multicoloring trees.
Information and Computation | 2003-08-19 | Paper |
| scientific article; zbMATH DE number 1875415 (Why is no real title available?) | 2003-03-02 | Paper |
Online independent sets.
Theoretical Computer Science | 2003-01-21 | Paper |
Approximating theDomatic Number
SIAM Journal on Computing | 2003-01-05 | Paper |
| scientific article; zbMATH DE number 1833406 (Why is no real title available?) | 2002-11-21 | Paper |
A matched approximation bound for the sum of a greedy coloring
Information Processing Letters | 2002-07-25 | Paper |
| scientific article; zbMATH DE number 1696636 (Why is no real title available?) | 2002-07-22 | Paper |
| Approximating Steiner trees in graphs with restricted weights | 2002-07-21 | Paper |
Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
Journal of Algorithms | 2002-07-11 | Paper |
Approximations for the general block distribution of a matrix
Theoretical Computer Science | 2002-03-03 | Paper |
On powers of chordal graphs and their colorings
Congressus Numerantium | 2002-01-08 | Paper |
On the approximability of the stable marriage problem
RIMS Kokyuroku | 2001-09-17 | Paper |
| scientific article; zbMATH DE number 1445362 (Why is no real title available?) | 2001-08-02 | Paper |
Approximation algorithms for dispersion problems
Journal of Algorithms | 2001-07-23 | Paper |
| scientific article; zbMATH DE number 1568052 (Why is no real title available?) | 2001-02-21 | Paper |
| scientific article; zbMATH DE number 1555958 (Why is no real title available?) | 2001-01-24 | Paper |
Greedy local improvement and weighted set packing approximation
Journal of Algorithms | 2001-01-01 | Paper |
Sum Multicoloring of Graphs
Journal of Algorithms | 2000-12-19 | Paper |
Approximations of Weighted Independent Set and Hereditary Subset Problems
Journal of Graph Algorithms and Applications | 2000-09-19 | Paper |
On the approximation of largest common subtrees and largest common point sets
Theoretical Computer Science | 2000-08-23 | Paper |
| scientific article; zbMATH DE number 1420902 (Why is no real title available?) | 2000-06-07 | Paper |
| scientific article; zbMATH DE number 1223713 (Why is no real title available?) | 2000-06-04 | Paper |
| scientific article; zbMATH DE number 1405687 (Why is no real title available?) | 2000-04-03 | Paper |
Independent sets with domination constraints
Discrete Applied Mathematics | 2000-03-20 | Paper |
| scientific article; zbMATH DE number 1418267 (Why is no real title available?) | 2000-03-19 | Paper |
Online coloring known graphs
The Electronic Journal of Combinatorics | 2000-03-12 | Paper |
Online coloring known graphs
The Electronic Journal of Combinatorics | 2000-03-12 | Paper |
Finding Subsets Maximizing Minimum Structures
SIAM Journal on Discrete Mathematics | 1999-11-23 | Paper |
| scientific article; zbMATH DE number 1305517 (Why is no real title available?) | 1999-11-21 | Paper |
| scientific article; zbMATH DE number 1354144 (Why is no real title available?) | 1999-10-31 | Paper |
| scientific article; zbMATH DE number 1305405 (Why is no real title available?) | 1999-06-17 | Paper |
| scientific article; zbMATH DE number 1301103 (Why is no real title available?) | 1999-06-15 | Paper |
| scientific article; zbMATH DE number 1182757 (Why is no real title available?) | 1998-12-10 | Paper |
On chromatic sums and distributed resource allocation
Information and Computation | 1998-09-27 | Paper |
Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
Journal of Graph Algorithms and Applications | 1998-04-01 | Paper |
Greed is good: Approximating independent sets in sparse and bounded-degree graphs
Algorithmica | 1997-07-20 | Paper |
Parallel and On-Line Graph Coloring
Journal of Algorithms | 1997-06-23 | Paper |
| scientific article; zbMATH DE number 910870 (Why is no real title available?) | 1996-08-22 | Paper |
| scientific article; zbMATH DE number 910871 (Why is no real title available?) | 1996-07-28 | Paper |
| scientific article; zbMATH DE number 753971 (Why is no real title available?) | 1995-08-06 | Paper |
| scientific article; zbMATH DE number 742967 (Why is no real title available?) | 1995-04-11 | Paper |
Lower bounds for on-line graph coloring
Theoretical Computer Science | 1994-08-29 | Paper |
Approximating the tree and tour covers of a graph
Information Processing Letters | 1994-01-16 | Paper |
Approximating the minimum maximal independence number
Information Processing Letters | 1994-01-09 | Paper |
A still better performance guarantee for approximate graph coloring
Information Processing Letters | 1993-05-16 | Paper |
Approximating maximum independent sets by excluding subgraphs
BIT | 1992-12-14 | Paper |
| scientific article; zbMATH DE number 65708 (Why is no real title available?) | 1992-09-27 | Paper |
