Magnús M. Halldórsson

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Superfast coloring in CONGEST via efficient color sampling.

[BibT_eX]

[DOI]

Theor. Comput. Sci., February, 2023

SIROCCO Prize for Innovation in Distributed Computing - Laudatio for Boaz Patt-Shamir.

[BibT_eX]

[DOI]

Bull. EATCS, 2023

Fast Coloring Despite Congested Relays.

[BibT_eX]

[DOI]

Maxime Flin

Proceedings of the 37th International Symposium on Distributed Computing, 2023

Coloring Fast with Broadcasts.

[BibT_eX]

[DOI]

Maxime Flin

Mohsen Ghaffari

Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

Fast Distributed Brooks' Theorem.

[BibT_eX]

[DOI]

Manuela Fischer

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Distributed Coloring of Hypergraphs.

[BibT_eX]

[DOI]

Duncan Adamson

Proceedings of the Structural Information and Communication Complexity, 2023

2022

Posimodular Function Optimization.

[BibT_eX]

[DOI]

Toshimasa Ishii

Kazuhisa Makino

Kenjiro Takazawa

Algorithmica, 2022

Fast Distributed Vertex Splitting with Applications.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Near-optimal distributed degree+1 coloring.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Overcoming Congestion in Distributed Coloring.

[BibT_eX]

[DOI]

Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

2021

Query-competitive sorting with uncertainty.

[BibT_eX]

[DOI]

Murilo Santos de Lima

Theor. Comput. Sci., 2021

Query minimization under stochastic uncertainty.

[BibT_eX]

[DOI]

Steven Chaplick

Murilo S. de Lima

Theor. Comput. Sci., 2021

Sparse Backbone and Optimal Distributed SINR Algorithms.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

Effective Wireless Scheduling via Hypergraph Sketches.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Local improvement algorithms for a path packing problem: A performance analysis based on linear programming.

[BibT_eX]

[DOI]

Koen M. J. De Bontridder

Oper. Res. Lett., 2021

Computing inductive vertex orderings.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2021

Ultrafast Distributed Coloring of High Degree Graphs.

[BibT_eX]

[DOI]

CoRR, 2021

Network Design under General Wireless Interference.

[BibT_eX]

[DOI]

Algorithmica, 2021

Generalized Disk Graphs.

[BibT_eX]

[DOI]

Ívar Marrow Arnþórsson

Steven Chaplick

Jökull Snær Gylfason

Jökull Máni Reynisson

Proceedings of the Algorithms and Data Structures - 17th International Symposium, 2021

Efficient randomized distributed coloring in CONGEST.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

Limitations of current wireless link scheduling algorithms.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Improved distributed algorithms for coloring interval graphs with application to multicoloring trees.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Leader election in SINR model with arbitrary power control.

[BibT_eX]

[DOI]

Evangelia Anna Markatou

Nancy A. Lynch

Theor. Comput. Sci., 2020

Radio aggregation scheduling.

[BibT_eX]

[DOI]

Hoon Oh

Theor. Comput. Sci., 2020

Simple and local independent set approximation.

[BibT_eX]

[DOI]

Ravi B. Boppana

Theor. Comput. Sci., 2020

Coloring Fast Without Learning Your Neighbors' Colors.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems.

[BibT_eX]

[DOI]

Marek Cygan

Proceedings of the Approximation and Online Algorithms - 18th International Workshop, 2020

Distributed Testing of Distance-k Colorings.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2020

Distance-2 Coloring in the CONGEST Model.

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

2019

Wireless Network Algorithmics.

[BibT_eX]

[DOI]

Proceedings of the Computing and Software Science - State of the Art and Perspectives, 2019

Leveraging multiple channels in ad hoc networks.

[BibT_eX]

[DOI]

Distributed Comput., 2019

Distributed approximation of k-service assignment.

[BibT_eX]

[DOI]

Sven Köhler

Distributed Comput., 2019

Link Scheduling under Correlated Shadowing.

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Modeling and Optimization in Mobile, 2019

The Capacity of Smartphone Peer-To-Peer Networks.

[BibT_eX]

[DOI]

Michael Dinitz

Alex Weaver

Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Plain SINR is Enough!

[BibT_eX]

[DOI]

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Distributed Minimum Degree Spanning Trees.

[BibT_eX]

[DOI]

Michael Dinitz

Taisuke Izumi

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2018

Special issue for the 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015, Kyoto, Japan.

[BibT_eX]

[DOI]

Naoki Kobayashi

Bettina Speckmann

Inf. Comput., 2018

Distributed backup placement in networks.

[BibT_eX]

[DOI]

Sven Köhler

Distributed Comput., 2018

Computing large independent sets in a single round.

[BibT_eX]

[DOI]

Distributed Comput., 2018

Scheduling (Dagstuhl Seminar 18101).

[BibT_eX]

[DOI]

Nicole Megow

Clifford Stein

Dagstuhl Reports, 2018

Distributed Algorithms for Minimum Degree Spanning Trees.

[BibT_eX]

[DOI]

Michael Dinitz

CoRR, 2018

Leveraging Indirect Signaling for Topology Inference and Fast Broadcast.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Session details: Session 3C: Coloring.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Brief Announcement: Simple and Local Independent Set Approximation.

[BibT_eX]

[DOI]

Ravi B. Boppana

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Wireless Aggregation at Nearly Constant Rate.

[BibT_eX]

[DOI]

Proceedings of the 38th IEEE International Conference on Distributed Computing Systems, 2018

Spanning Trees With Edge Conflicts and Wireless Connectivity.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Algorithms for Chromatic Sums, Multicoloring, and Scheduling Dependent Jobs.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

2017

The Power of Oblivious Wireless Power.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Max point-tolerance graphs.

[BibT_eX]

[DOI]

Daniele Catanzaro

Steven Chaplick

Stefan Felsner

Thomas Hixon

Juraj Stacho

Discret. Appl. Math., 2017

Foundations of Wireless Networking (Dagstuhl Seminar 17271).

[BibT_eX]

[DOI]

Christina Fragouli

Kyle Jamieson

Bhaskar Krishnamachari

Dagstuhl Reports, 2017

Universal Framework for Wireless Scheduling Problems.

[BibT_eX]

[DOI]

CoRR, 2017

An Efficient Communication Abstraction for Dense Wireless Networks.

[BibT_eX]

[DOI]

Nancy A. Lynch

Proceedings of the 31st International Symposium on Distributed Computing, 2017

Leader Election in SINR Model with Arbitrary Power Control.

[BibT_eX]

[DOI]

Evangelia Anna Markatou

Proceedings of the Structural Information and Communication Complexity, 2017

Brief Announcement: Leader Election in SINR Model with Arbitrary Power Control.

[BibT_eX]

[DOI]

Evangelia Anna Markatou

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Aggregation Rate for Compressible Functions.

[BibT_eX]

[DOI]

Proceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2017

Wireless Link Capacity under Shadowing and Fading.

[BibT_eX]

[DOI]

Proceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2017

Dynamic Adaptation in Wireless Networks Under Comprehensive Interference via Carrier Sense.

[BibT_eX]

[DOI]

Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium, 2017

Universal Framework for Wireless Scheduling Problems.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Space-Constrained Interval Selection.

[BibT_eX]

[DOI]

Yuval Emek

Adi Rosén

ACM Trans. Algorithms, 2016

The minimum vulnerability problem on specific graph classes.

[BibT_eX]

[DOI]

Yusuke Aoki

Takehiro Ito

Xiao Zhou

J. Comb. Optim., 2016

Nearly optimal bounds for distributed wireless scheduling in the SINR model.

[BibT_eX]

[DOI]

Distributed Comput., 2016

Semi-transitive orientations and word-representable graphs.

[BibT_eX]

[DOI]

Sergey Kitaev

Artem V. Pyatkin

Discret. Appl. Math., 2016

On the complexity of the shortest-path broadcast problem.

[BibT_eX]

[DOI]

Pierluigi Crescenzi

Hovhannes A. Harutyunyan

Chiara Pierucci

Andrea Pietracaprina

Geppino Pucci

Discret. Appl. Math., 2016

Data Dissemination in Unified Dynamic Wireless Networks.

[BibT_eX]

[DOI]

CoRR, 2016

Streaming Algorithms for Independent Sets in Sparse Hypergraphs.

[BibT_eX]

[DOI]

Algorithmica, 2016

Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems.

[BibT_eX]

[DOI]

Adi Rosén

Algorithmica, 2016

Invited paper: Models for wireless algorithms.

[BibT_eX]

[DOI]

Proceedings of the 14th International Symposium on Modeling and Optimization in Mobile, 2016

Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Brief Announcement: Local Independent Set Approximation.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

2015

Guest editorial: Structural Information and Communication Complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Vertex coloring edge-weighted digraphs.

[BibT_eX]

[DOI]

Jørgen Bang-Jensen

Inf. Process. Lett., 2015

Distributed Large Independent Sets in One Round on Bounded-Independence Graphs.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 29th International Symposium, 2015

How Well Can Graphs Represent Wireless Interference?

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Progress (and Lack Thereof) for Graph Coloring Approximation Problems.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2015: Theory and Practice of Computer Science, 2015

A Local Broadcast Layer for the SINR Network Model.

[BibT_eX]

[DOI]

Nancy A. Lynch

Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

The Price of Local Power Control in Wireless Scheduling.

[BibT_eX]

[DOI]

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

Limitations of Current Wireless Scheduling Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithms for Sensor Systems, 2015

2014

Algorithms for Wireless Capacity.

[BibT_eX]

[DOI]

Olga Goussevskaia

IEEE/ACM Trans. Netw., 2014

Wireless capacity with arbitrary gain matrix.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

Editorial for Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities.

[BibT_eX]

[DOI]

Thomas Erlebach

Sotiris E. Nikoletseas

Pekka Orponen

Theor. Comput. Sci., 2014

Making wireless algorithm theory more useful: five ideas from the 2013 workshop on realistic models for algorithms in wireless networks.

[BibT_eX]

[DOI]

SIGACT News, 2014

Report on Two events at ICE-TCS, Reykjavik University.

[BibT_eX]

[DOI]

Luca Aceto

Anna Ingólfsdóttir

Bull. EATCS, 2014

Measurement Based Interference Models for Wireless Scheduling Algorithms.

[BibT_eX]

[DOI]

Helga Gudmundsdottir

Joseph T. Foley

Geir M. Järvelä

Henning Úlfarsson

Ymir Vigfusson

CoRR, 2014

Maximum MIMO Flow in wireless networks under the SINR model.

[BibT_eX]

[DOI]

Proceedings of the 12th International Symposium on Modeling and Optimization in Mobile, 2014

Distributed Algorithms for Coloring Interval Graphs.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 28th International Symposium, 2014

Beyond geometry: towards fully realistic wireless models.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Extending wireless algorithm design to arbitrary environments via metricity.

[BibT_eX]

[DOI]

Helga Gudmundsdottir

Joseph T. Foley

Ymir Vigfusson

Proceedings of the 17th ACM International Conference on Modeling, 2014

The Minimum Vulnerability Problem on Graphs.

[BibT_eX]

[DOI]

Yusuke Aoki

Takehiro Ito

Xiao Zhou

Proceedings of the Combinatorial Optimization and Applications, 2014

2013

Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees.

[BibT_eX]

[DOI]

Tatsuya Akutsu

Daiji Fukagawa

Atsuhiro Takasu

Keisuke Tanaka

Theor. Comput. Sci., 2013

SDP-based algorithms for maximum independent set problems on hypergraphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Corrigendum: Improved results for data migration and open shop scheduling.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2013

Online Scheduling with Interval Conflicts.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2013

Online selection of intervals and t-intervals.

[BibT_eX]

[DOI]

Unnar Th. Bachmann

Inf. Comput., 2013

Editorial.

[BibT_eX]

[DOI]

Camil Demetrescu

Algorithmica, 2013

Brief announcement: locality in wireless scheduling.

[BibT_eX]

[DOI]

Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

The Power of Non-Uniform Wireless Power.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Connectivity and aggregation in multihop wireless networks.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

Modeling Reality Algorithmically: The Case of Wireless Communication.

[BibT_eX]

[DOI]

Proceedings of the Algorithms for Sensor Systems, 2013

2012

Wireless scheduling with power control.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

Online Set Packing.

[BibT_eX]

[DOI]

Yuval Emek

Yishay Mansour

SIAM J. Comput., 2012

Wireless connectivity and capacity.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Wireless Network Stability in the SINR Model.

[BibT_eX]

[DOI]

Eyjolfur Ingi Asgeirsson

Proceedings of the Structural Information and Communication Complexity, 2012

Distributed connectivity of wireless networks.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

Brief announcement: distributed algorithms for throughput performance in wireless networks.

[BibT_eX]

[DOI]

Eyjolfur Ingi Asgeirsson

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

On the Impact of Identifiers on Local Decision.

[BibT_eX]

[DOI]

Amos Korman

Proceedings of the Principles of Distributed Systems, 16th International Conference, 2012

Wireless capacity and admission control in cognitive radio.

[BibT_eX]

[DOI]

Proceedings of the IEEE INFOCOM 2012, Orlando, FL, USA, March 25-30, 2012, 2012

Streaming and Communication Complexity of Clique Approximation.

[BibT_eX]

[DOI]

Xiaoming Sun

Chengu Wang

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Towards tight bounds for local broadcasting.

[BibT_eX]

[DOI]

Proceedings of the FOMC'12, 2012

A fully distributed algorithm for throughput performance in wireless networks.

[BibT_eX]

[DOI]

Eyjolfur Ingi Asgeirsson

Proceedings of the 46th Annual Conference on Information Sciences and Systems, 2012

2011

Sum edge coloring of multigraphs via configuration LP.

[BibT_eX]

[DOI]

Maxim Sviridenko

ACM Trans. Algorithms, 2011

Algorithms for Weighted Capacity and Admission Control in Wireless Networks

[BibT_eX]

[DOI]

CoRR, 2011

Alternation Graphs.

[BibT_eX]

[DOI]

Sergey Kitaev

Artem V. Pyatkin

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

Wireless Capacity with Oblivious Power in General Metrics.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

Online coloring of hypergraphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2010

Vertex coloring the square of outerplanar graphs of low degree.

[BibT_eX]

[DOI]

Discuss. Math. Graph Theory, 2010

On spectrum sharing games.

[BibT_eX]

[DOI]

Joseph Y. Halpern

Li Erran Li

Vahab S. Mirrokni

Distributed Comput., 2010

Online Selection of Intervals and <i>t</i>-Intervals.

[BibT_eX]

[DOI]

Unnar Th. Bachmann

Proceedings of the Algorithm Theory, 2010

Online set packing and competitive scheduling of multi-part tasks.

[BibT_eX]

[DOI]

Yuval Emek

Yishay Mansour

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Streaming Algorithms for Independent Sets.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Return of the Boss Problem: Competing Online against a Non-adaptive Adversary.

[BibT_eX]

[DOI]

Proceedings of the Fun with Algorithms, 5th International Conference, 2010

Graphs Capturing Alternations in Words.

[BibT_eX]

[DOI]

Sergey Kitaev

Artem V. Pyatkin

Proceedings of the Developments in Language Theory, 14th International Conference, 2010

2009

Scheduling with conflicts: online and offline algorithms.

[BibT_eX]

[DOI]

Guy Even

Lotem Kaplan

Dana Ron

J. Sched., 2009

Approximation algorithms for the weighted independent set problem in sparse graphs.

[BibT_eX]

[DOI]

Akihisa Kako

Takao Ono

Tomio Hirata

Discret. Appl. Math., 2009

Independent sets in bounded-degree hypergraphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.

[BibT_eX]

[DOI]

Leah Epstein

Asaf Levin

Algorithmica, 2009

Capacity of Arbitrary Wireless Networks.

[BibT_eX]

[DOI]

Olga Goussevskaia

Emo Welzl

Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009

Wireless Communication Is in APX.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Minimizing interference of a wireless ad-hoc network in a plane.

[BibT_eX]

[DOI]

Takeshi Tokuyama

Theor. Comput. Sci., 2008

Improved bounds for scheduling conflicting jobs with minsum criteria.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2008

Vertex coloring acyclic digraphs and their corresponding hypergraphs.

[BibT_eX]

[DOI]

Ágúst S. Egilsson

Discret. Appl. Math., 2008

Batch Coloring Flat Graphs and Thin.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2008

Robust cost colorings.

[BibT_eX]

[DOI]

Takuro Fukunaga

Hiroshi Nagamochi

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Min Sum Edge Coloring in Multigraphs Via Configuration LP.

[BibT_eX]

[DOI]

Maxim Sviridenko

Proceedings of the Integer Programming and Combinatorial Optimization, 2008

2007

Improved approximation results for the stable marriage problem.

[BibT_eX]

[DOI]

Hiroki Yanagisawa

ACM Trans. Algorithms, 2007

Strongly simplicial vertices of powers of trees.

[BibT_eX]

[DOI]

Discret. Math., 2007

Complete partitions of graphs.

[BibT_eX]

[DOI]

Sivaramakrishnan Sivasubramanian

Comb., 2007

Fixed-Parameter Tractability for Non-Crossing Spanning Trees.

[BibT_eX]

[DOI]

Christian Knauer

Andreas Spillner

Takeshi Tokuyama

Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

"Rent-or-Buy" Scheduling and Cost Coloring Problems.

[BibT_eX]

[DOI]

Takuro Fukunaga

Hiroshi Nagamochi

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

2006

Improved results for data migration and open shop scheduling.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2006

Scheduling Split Intervals.

[BibT_eX]

[DOI]

Reuven Bar-Yehuda

Joseph Naor

Irina Shapira

SIAM J. Comput., 2006

Strip Graphs: Recognition and Scheduling.

[BibT_eX]

[DOI]

Ragnar K. Karlsson

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

2005

Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth.

[BibT_eX]

[DOI]

Artur Czumaj

Andrzej Lingas

Johan Nilsson

Inf. Process. Lett., 2005

Approximation Algorithms for the Weighted Independent Set Problem.

[BibT_eX]

[DOI]

Akihisa Kako

Takao Ono

Tomio Hirata

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2005

2004

Randomized approximation of the stable marriage problem.

[BibT_eX]

[DOI]

Hiroki Yanagisawa

Theor. Comput. Sci., 2004

Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

Strong Colorings of Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

On colorings of squares of outerplanar graphs.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Multicoloring: Problems and Techniques.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

2003

Approximability results for stable marriage problems with ties.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Coloring Powers of Planar Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2003

Approximation algorithms for the test cover problem.

[BibT_eX]

[DOI]

Koen M. J. De Bontridder

Math. Program., 2003

Multicoloring trees.

[BibT_eX]

[DOI]

Inf. Comput., 2003

Powers of geometric intersection graphs and dispersion algorithms.

[BibT_eX]

[DOI]

Peter Damaschke

Discret. Appl. Math., 2003

Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs.

[BibT_eX]

[DOI]

Algorithmica, 2003

Improved Approximation of the Stable Marriage Problem.

[BibT_eX]

[DOI]

Hiroki Yanagisawa

Proceedings of the Algorithms, 2003

Proper Down-Coloring Simple Acyclic Digraphs.

[BibT_eX]

[DOI]

Ágúst S. Egilsson

Proceedings of the Applications of Graph Transformations with Industrial Relevance, 2003

2002

Online independent sets.

[BibT_eX]

[DOI]

Shiro Taketomi

Theor. Comput. Sci., 2002

Approximating the Domatic Number.

[BibT_eX]

[DOI]

Uriel Feige

Aravind Srinivasan

SIAM J. Comput., 2002

Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees.

[BibT_eX]

[DOI]

J. Algorithms, 2002

Inapproximability Results on Stable Marriage Problems.

[BibT_eX]

[DOI]

Yasufumi Morita

Proceedings of the LATIN 2002: Theoretical Informatics, 2002

2001

Approximations for the general block distribution of a matrix.

[BibT_eX]

[DOI]

Bengt Aspvall

Fredrik Manne

Theor. Comput. Sci., 2001

Greedy Local Improvement and Weighted Set Packing Approximation.

[BibT_eX]

[DOI]

Barun Chandra

J. Algorithms, 2001

Approximation Algorithms for Dispersion Problems.

[BibT_eX]

[DOI]

Barun Chandra

J. Algorithms, 2001

Minimizing Average Completion of Dedicated Tasks and Interval Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

On the Approximability of the Minimum Test Collection Problem.

[BibT_eX]

[DOI]

R. Ravi

Proceedings of the Algorithms, 2001

Logical Form Equivalence: the Case of Referring Expressions Generation.

[BibT_eX]

[DOI]

Kees van Deemter

Proceedings of the ACL 2001 Eighth European Workshop on Natural Language Generation, 2001

2000

On the approximation of largest common subtrees and largest common point sets.

[BibT_eX]

[DOI]

Tatsuya Akutsu

Theor. Comput. Sci., 2000

Guest Editor's Foreword.

[BibT_eX]

Nord. J. Comput., 2000

Approximations of Weighted Independent Set and Hereditary Subset Problems.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2000

Sum Multicoloring of Graphs.

[BibT_eX]

[DOI]

Ravit Salman

J. Algorithms, 2000

Mod-2 Independence and Domination in Graphs.

[BibT_eX]

[DOI]

Jan Kratochvíl

Jan Arne Telle

Int. J. Found. Comput. Sci., 2000

Independent Sets with Domination Constraints.

[BibT_eX]

[DOI]

Jan Kratochvíl

Jan Arne Telle

Discret. Appl. Math., 2000

Online Coloring Known Graphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2000

Approximating the domatic number.

[BibT_eX]

[DOI]

Uriel Feige

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits.

[BibT_eX]

[DOI]

Takao Asano

Takeshi Matsuda

Proceedings of the Algorithms and Computation, 11th International Conference, 2000

1999

Finding Subsets Maximizing Minimum Structures.

[BibT_eX]

[DOI]

Kazuo Iwano

Naoki Katoh

Takeshi Tokuyama

SIAM J. Discret. Math., 1999

A Matched Approximation Bound for the Sum of a Greedy Coloring.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

Multicoloring Planar Graphs and Partial k-Trees.

[BibT_eX]

[DOI]

Proceedings of the Randomization, 1999

Sum Multi-coloring of Graphs.

[BibT_eX]

[DOI]

Ravit Salman

Proceedings of the Algorithms, 1999

Multi-coloring Trees.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998

Approximating Steiner trees in graphs with restricted weights.

[BibT_eX]

[DOI]

Shuichi Ueno

Hiroshi Nakao

Yoji Kajitani

Networks, 1998

On Chromatic Sums and Distributed Resource Allocation.

[BibT_eX]

[DOI]

Mihir Bellare

Tami Tamir

Inf. Comput., 1998

Approximations of Independent Sets in Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997

Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring.

[BibT_eX]

[DOI]

Hoong Chuin Lau

J. Graph Algorithms Appl., 1997

Parallel and On-Line Graph Coloring.

[BibT_eX]

[DOI]

J. Algorithms, 1997

Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs.

[BibT_eX]

[DOI]

Algorithmica, 1997

1996

Facility Dispersion and Remote Subgraphs.

[BibT_eX]

[DOI]

Barun Chandra

Proceedings of the Algorithm Theory, 1996

Approximation and Special Cases of Common Subtrees and Editing Distance.

[BibT_eX]

[DOI]

Keisuke Tanaka

Proceedings of the Algorithms and Computation, 7th International Symposium, 1996

Approximating <i>k</i>-Set Cover and Complementary Graph Coloring.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 1996

1995

Approximating Discrete Collections via Local Improvements.

[BibT_eX]

[DOI]

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Greedy Approximations of Independent Sets in Low Degree Graphs.

[BibT_eX]

[DOI]

Kiyohito Yoshihara

Proceedings of the Algorithms and Computation, 6th International Symposium, 1995

1994

Lower Bounds for On-Line Graph Coloring.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

Improved Approximations of Independent Sets in Bounded-Degree Graphs via Subgraph Removal.

[BibT_eX]

Nord. J. Comput., 1994

Improved Approximations of Independent Sets in Bounded-Degree Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1994

1993

Approximating the Minimum Maximal Independence Number.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1993

A Still Better Performance Guarantee for Approximate Graph Coloring.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1993

Approximating the Tree and Tour Covers of a Graph.

[BibT_eX]

[DOI]

Esther M. Arkin

Refael Hassin

Inf. Process. Lett., 1993

On Some Communication Complexity Problems Related to THreshold Functions.

[BibT_eX]

[DOI]

K. V. Subrahmanyam

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1993

Directed vs. Undirected Monotone Contact Networks for Threshold Functions

[BibT_eX]

[DOI]

K. V. Subrahmanyam

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Approximating Maximum Independent Sets by Excluding Subgraphs.

[BibT_eX]

[DOI]

Ravi B. Boppana

BIT, 1992

Parallel and On-line Graph Coloring Algorithms.

[BibT_eX]

[DOI]