5-Regular Graphs are 3-Colorable with Positive Probability (English)
- New search for: Díaz, J.
- New search for: Grammatikopoulos, G.
- New search for: Kaporis, A. C.
- New search for: Kirousis, L. M.
- New search for: Pérez, X.
- New search for: Sotiropoulos, D. G.
- New search for: Díaz, J.
- New search for: Grammatikopoulos, G.
- New search for: Kaporis, A. C.
- New search for: Kirousis, L. M.
- New search for: Pérez, X.
- New search for: Sotiropoulos, D. G.
In:
Algorithms – ESA 2005
;
215-225
;
2005
- Article/Chapter (Book) / Electronic Resource
-
Title:5-Regular Graphs are 3-Colorable with Positive Probability
-
Contributors:Díaz, J. ( author ) / Grammatikopoulos, G. ( author ) / Kaporis, A. C. ( author ) / Kirousis, L. M. ( author ) / Pérez, X. ( author ) / Sotiropoulos, D. G. ( author )
-
Published in:Algorithms – ESA 2005 ; 215-225Lecture Notes in Computer Science ; 3669 ; 215-225
-
Publisher:
- New search for: Springer Berlin Heidelberg
-
Place of publication:Berlin, Heidelberg
-
Publication date:2005-01-01
-
Size:11 pages
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Article/Chapter (Book)
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Source:
Table of contents eBook
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
Designing Reliable Algorithms in Unreliable MemoriesFinocchi, Irene / Grandoni, Fabrizio / Italiano, Giuseppe F. et al. | 2005
- 9
-
From Balanced Graph Partitioning to Balanced Metric LabelingNaor, Joseph et al. | 2005
- 10
-
Fearful Symmetries: Quantum Computing, Factoring, and Graph IsomorphismMoore, Cristopher et al. | 2005
- 11
-
Exploring an Unknown Graph EfficientlyFleischer, Rudolf / Trippen, Gerhard et al. | 2005
- 23
-
Online Routing in Faulty Meshes with Sub-linear Comparative Time and Traffic RatioRührup, Stefan / Schindelhauer, Christian et al. | 2005
- 35
-
Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum MulticutBatra, Garima / Garg, Naveen / Gupta, Garima et al. | 2005
- 47
-
Relax-and-Cut for Capacitated Network DesignKliewer, Georg / Timajev, Larissa et al. | 2005
- 59
-
On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games,,Christodoulou, George / Koutsoupias, Elias et al. | 2005
- 71
-
The Complexity of Games on Highly Regular GraphsDaskalakis, Konstantinos / Papadimitriou, Christos H. et al. | 2005
- 83
-
Computing Equilibrium Prices: Does Theory Meet Practice?Codenotti, Bruno / McCune, Benton / Raman, Rajiv / Varadarajan, Kasturi et al. | 2005
- 95
-
Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch DecompositionsDorn, Frederic / Penninkx, Eelko / Bodlaender, Hans L. / Fomin, Fedor V. et al. | 2005
- 107
-
An Algorithm for the SAT Problem for Formulae of Linear LengthWahlström, Magnus et al. | 2005
- 119
-
Linear-Time Enumeration of Isolated CliquesIto, Hiro / Iwama, Kazuo / Osumi, Tsuyoshi et al. | 2005
- 131
-
Finding Shortest Non-separating and Non-contractible Cycles for Topologically Embedded GraphsCabello, Sergio / Mohar, Bojan et al. | 2005
- 143
-
Delineating Boundaries for Imprecise RegionsReinbacher, Iris / Benkert, Marc / Kreveld, Marc / Mitchell, Joseph S. B. / Wolff, Alexander et al. | 2005
- 155
-
Exacus: Efficient and Exact Algorithms for Curves and SurfacesBerberich, Eric / Eigenwillig, Arno / Hemmer, Michael / Hert, Susan / Kettner, Lutz / Mehlhorn, Kurt / Reichel, Joachim / Schmitt, Susanne / Schömer, Elmar / Wolpert, Nicola et al. | 2005
- 167
-
Min Sum Clustering with PenaltiesHassin, Refael / Or, Einat et al. | 2005
- 179
-
Improved Approximation Algorithms for Metric Max TSPChen, Zhi-Zhong / Nagoya, Takayuki et al. | 2005
- 191
-
Unbalanced Graph CutsHayrapetyan, Ara / Kempe, David / Pál, Martin / Svitkina, Zoya et al. | 2005
- 203
-
Low Degree Connectivity in Ad-Hoc NetworksKučera, Luděk et al. | 2005
- 215
-
5-Regular Graphs are 3-Colorable with Positive ProbabilityDíaz, J. / Grammatikopoulos, G. / Kaporis, A. C. / Kirousis, L. M. / Pérez, X. / Sotiropoulos, D. G. et al. | 2005
- 226
-
Optimal Integer Alphabetic Trees in Linear TimeHu, T. C. / Larmore, Lawrence L. / Morgenthaler, J. David et al. | 2005
- 238
-
Predecessor Queries in Constant Time?Karpinski, Marek / Nekrich, Yakov et al. | 2005
- 249
-
An Algorithm for Node-Capacitated Ring RoutingFrank, András / Király, Zoltán / Kotnyek, Balázs et al. | 2005
- 259
-
On Degree Constrained Shortest PathsKhuller, Samir / Lee, Kwangil / Shayman, Mark et al. | 2005
- 271
-
A New Template for Solving p-Median Problems for Trees in Sub-quadratic TimeBenkoczi, Robert / Bhattacharya, Binay et al. | 2005
- 283
-
Roll Cutting in the Curtain IndustryAlfieri, Arianna / Velde, Steef L. / Woeginger, Gerhard J. et al. | 2005
- 293
-
Space Efficient Algorithms for the Burrows-Wheeler BacktransformationLauther, Ulrich / Lukovszki, Tamás et al. | 2005
- 305
-
Cache-Oblivious Comparison-Based Algorithms on MultisetsFarzan, Arash / Ferragina, Paolo / Franceschini, Gianni / Munro, J. Ian et al. | 2005
- 317
-
Oblivious vs. Distribution-Based Sorting: An Experimental EvaluationChaudhry, Geeta / Cormen, Thomas H. et al. | 2005
- 329
-
Allocating Memory in a Lock-Free MannerGidenstam, Anders / Papatriantafilou, Marina / Tsigas, Philippas et al. | 2005
- 343
-
Generating Realistic Terrains with Higher-Order Delaunay TriangulationsKok, Thierry / Kreveld, Marc / Löffler, Maarten et al. | 2005
- 355
-
I/O-Efficient Construction of Constrained Delaunay TriangulationsAgarwal, Pankaj K. / Arge, Lars / Yi, Ke et al. | 2005
- 367
-
Convex Hull and Voronoi Diagram of Additively Weighted PointsBoissonnat, Jean-Daniel / Delage, Christophe et al. | 2005
- 379
-
New Tools and Simpler Algorithms for BranchwidthPaul, Christophe / Telle, Jan Arne et al. | 2005
- 391
-
Treewidth Lower Bounds with BramblesBodlaender, Hans L. / Grigoriev, Alexander / Koster, Arie M. C. A. et al. | 2005
- 403
-
Minimal Interval CompletionsHeggernes, Pinar / Suchan, Karol / Todinca, Ioan / Villanger, Yngve et al. | 2005
- 415
-
A 2-Approximation Algorithm for Sorting by Prefix ReversalsFischer, Johannes / Ginzinger, Simon W. et al. | 2005
- 426
-
Approximating the 2-Interval Pattern ProblemCrochemore, Maxime / Hermelin, Danny / Landau, Gad M. / Vialette, Stéphane et al. | 2005
- 438
-
A Loopless Gray Code for Minimal Signed-Binary RepresentationsManku, Gurmeet Singh / Sawada, Joe et al. | 2005
- 448
-
Efficient Approximation Schemes for Geometric Problems?Marx, Dániel et al. | 2005
- 460
-
Geometric Clustering to Minimize the Sum of Cluster SizesBilò, Vittorio / Caragiannis, Ioannis / Kaklamanis, Christos / Kanellopoulos, Panagiotis et al. | 2005
- 472
-
Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar GraphsBerger, André / Czumaj, Artur / Grigni, Michelangelo / Zhao, Hairong et al. | 2005
- 484
-
Packet Routing and Information Gathering in Lines, Rings and TreesAzar, Yossi / Zachut, Rafi et al. | 2005
- 496
-
Jitter Regulation for Multiple StreamsHay, David / Scalosub, Gabriel et al. | 2005
- 508
-
Efficient c-Oriented Range Searching with DOP-TreesBerg, Mark / Haverkort, Herman / Streppel, Micha et al. | 2005
- 520
-
Matching Point Sets with Respect to the Earth Mover’s DistanceCabello, Sergio / Giannopoulos, Panos / Knauer, Christian / Rote, Günter et al. | 2005
- 532
-
Small Stretch Spanners on Dynamic GraphsAusiello, Giorgio / Franciosa, Paolo G. / Italiano, Giuseppe F. et al. | 2005
- 544
-
An Experimental Study of Algorithms for Fully Dynamic Transitive ClosureKrommidas, Ioannis / Zaroliagis, Christos et al. | 2005
- 556
-
Experimental Study of Geometric t-SpannersFarshi, Mohammad / Gudmundsson, Joachim et al. | 2005
- 568
-
Highway Hierarchies Hasten Exact Shortest Path QueriesSanders, Peter / Schultes, Dominik et al. | 2005
- 580
-
Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration DelaysFishkin, Aleksei V. / Jansen, Klaus / Sevastyanov, Sergey V. / Sitters, René et al. | 2005
- 592
-
Fairness-Free Periodic Scheduling with VacationsSgall, Jiří / Shachnai, Hadas / Tamir, Tami et al. | 2005
- 604
-
Online Bin Packing with Cardinality ConstraintsEpstein, Leah et al. | 2005
- 616
-
Fast Monotone 3-Approximation Algorithm for Scheduling Related MachinesKovács, Annamária et al. | 2005
- 628
-
Engineering Planar Separator AlgorithmsHolzer, Martin / Prasinos, Grigorios / Schulz, Frank / Wagner, Dorothea / Zaroliagis, Christos et al. | 2005
- 640
-
Stxxl: Standard Template Library for XXL Data SetsDementiev, Roman / Kettner, Lutz / Sanders, Peter et al. | 2005
- 652
-
Negative Cycle Detection ProblemWong, Chi-Him / Tam, Yiu-Cheong et al. | 2005
- 664
-
An Optimal Algorithm for Querying Priced Information: Monotone Boolean Functions and Game TreesCicalese, Ferdinando / Laber, Eduardo Sany et al. | 2005
- 677
-
Online View Maintenance Under a Response-Time ConstraintMunagala, Kamesh / Yang, Jun / Yu, Hai et al. | 2005
- 689
-
Online Primal-Dual Algorithms for Covering and Packing ProblemsBuchbinder, Niv / Naor, Joseph et al. | 2005
- 702
-
Efficient Algorithms for Shared Backup Allocation in Networks with Partial InformationBejerano, Yigal / Naor, Joseph / Sprintson, Alexander et al. | 2005
- 714
-
Using Fractional Primal-Dual to Schedule Split Intervals with DemandsBar-Yehuda, Reuven / Rawitz, Dror et al. | 2005
- 726
-
An Approximation Algorithm for the Minimum Latency Set Cover ProblemHassin, Refael / Levin, Asaf et al. | 2005
- 734
-
Workload-Optimal Histograms on StreamsMuthukrishnan, S. / Strauss, M. / Zheng, X. et al. | 2005
- 746
-
Finding Frequent Patterns in a String in Sublinear TimeBerenbrink, Petra / Ergun, Funda / Friedetzky, Tom et al. | 2005
- 758
-
Online Occlusion CullingFrahling, Gereon / Krokowski, Jens et al. | 2005
- 770
-
Shortest Paths in Matrix Multiplication TimeSankowski, Piotr et al. | 2005
- 779
-
Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of GraphsBergeron, Anne / Chauve, Cedric / Montgolfier, Fabien / Raffinot, Mathieu et al. | 2005
- 791
-
Greedy Routing in Tree-Decomposed GraphsFraigniaud, Pierre et al. | 2005
- 803
-
Making Chord Robust to Byzantine AttacksFiat, Amos / Saia, Jared / Young, Maxwell et al. | 2005
- 815
-
Bucket Game with Applications to Set Multicover and Dynamic Page MigrationBienkowski, Marcin / Byrka, Jarosław et al. | 2005
- 827
-
Bootstrapping a Hop-Optimal Network in the Weak Sensor ModelFarach-Colton, Martín / Fernandes, Rohan J. / Mosteiro, Miguel A. et al. | 2005
- 839
-
Approximating Integer Quadratic Programs and MAXCUT in Subdense GraphsBjörklund, Andreas et al. | 2005
- 850
-
A Cutting Planes Algorithm Based Upon a Semidefinite Relaxation for the Quadratic Assignment ProblemFaye, Alain / Roupin, Frédéric et al. | 2005
- 862
-
Approximation Complexity of min-max (Regret) Versions of Shortest Path, Spanning Tree, and KnapsackAissi, Hassene / Bazgan, Cristina / Vanderpooten, Daniel et al. | 2005
- 874
-
Robust Approximate ZerosSharma, Vikram / Du, Zilin / Yap, Chee K. et al. | 2005
- 887
-
Optimizing a 2D Function Satisfying Unimodality PropertiesDemaine, Erik D. / Langerman, Stefan et al. | 2005