Search results for "3-Coloring"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	Martin Kochol	Linear Algorithm for 3-Coloring of Locally Connected Graphs.	WEA	2003	DBLP DOI BibTeX RDF
2	Hans van Maaren, Linda van Norden	Hidden Threshold Phenomena for Fixed-Density SAT-formulae.	SAT	2003	DBLP DOI BibTeX RDF	Horn, graph-3-coloring, satisfiability, thresholds, 3-SAT
2	David Eppstein	Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.	SODA	2001	DBLP DOI BibTeX RDF
2	Eric Bach, Anne Condon, Elton Glaser, Celena Tanguay	DNA Models and Algorithms for NP-complete Problems. (PDF / PS)	IEEE Conference on Computational Complexity	1996	DBLP DOI BibTeX RDF	3Sat, 3-Coloring, Independent Set problem, DNA algorithms, genetic algorithms, computational complexity, search problems, DNA computing, DNA computation, NP-complete problems, search algorithms, NP-hard problems
2	Richard Beigel, David Eppstein	3-Coloring in Time O(1.3446n): A No-MIS Algorithm.	FOCS	1995	DBLP DOI BibTeX RDF	duality (mathematics), 3-coloring, worst case time bounds, 3-edge-coloring, 3-list-coloring, common generalization, symbol-system satisfiability, duality transformation, computational complexity, computability, decidability, NP-complete problems, graph colouring, time bounds, 3-SAT
2	Avrim Blum	Some Tools for Approximate 3-Coloring (Extended Abstract)	FOCS	1990	DBLP DOI BibTeX RDF	semirandom source, approximate 3-coloring, 3-chromatic graphs, noise rate, approximation algorithms, probability
1	Iztok Fister Jr., Iztok Fister, Janez Brest	A Hybrid Artificial Bee Colony Algorithm for Graph 3-Coloring.	ICAISC (SIDE-EC)	2012	DBLP DOI BibTeX RDF
1	N. S. Narayanaswamy, C. R. Subramanian	Dominating set based exact algorithms for 3-coloring.	Inf. Process. Lett.	2011	DBLP DOI BibTeX RDF
1	Lukasz Kowalik	Fast 3-coloring Triangle-Free Planar Graphs.	Algorithmica	2010	DBLP DOI BibTeX RDF
1	Jaroslaw Byrka, Andreas Karrenbauer, Laura Sanità	The Interval Constrained 3-Coloring Problem.	LATIN	2010	DBLP DOI BibTeX RDF
1	Andrzej Pezarski, Michal Zmarz	Non-Repetitive 3-Coloring of Subdivided Graphs.	Electr. J. Comb.	2009	DBLP BibTeX RDF
1	Jaroslaw Byrka, Andreas Karrenbauer, Laura Sanità	The interval constrained 3-coloring problem	CoRR	2009	DBLP BibTeX RDF
1	Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Alexey A. Stepanov	On Two Techniques of Combining Branching and Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Exact exponential time algorithms, #3-Coloring, #Minimum dominating set, Minimum maximal matching, k-Weighted vertex cover, NP hard problems, Treewidth, Parameterized algorithms
1	Zdenek Dvorak, Ken-ichi Kawarabayashi, Robin Thomas	Three-coloring triangle-free planar graphs in linear time.	SODA	2009	DBLP DOI BibTeX RDF
1	Zdenek Dvorak, Daniel Král, Robin Thomas	Coloring triangle-free graphs on surfaces.	SODA	2009	DBLP DOI BibTeX RDF
1	Kelun Wang, Hongxiang Ren, Shuang Wang	Study on Art Gallery Based on 4-coloring.	CGIV	2009	DBLP DOI BibTeX RDF
1	Hajo Broersma, Fedor V. Fomin, Petr A. Golovach, Daniël Paulusma	Three Complexity Results on Coloring Pk-Free Graphs.	IWOCA	2009	DBLP DOI BibTeX RDF	P k -free graph, computational complexity, graph coloring
1	Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A. Rosamond, Saket Saurabh	The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Max-leaf, Well-quasiordering, Bandwidth, Kernelization, Parameterized complexity
1	Xueliang Li, Wenli Zhou	The 2nd-order conditional 3-coloring of claw-free graphs.	Theor. Comput. Sci.	2008	DBLP DOI BibTeX RDF
1	Claudia Zepeda, José Luis Carballido	Computing of p-Stable Models Based on Semi-Negative Normal Programs with Constraints.	ENC	2008	DBLP DOI BibTeX RDF
1	Andreas Wiese, Evangelos Kranakis	Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs.	WG	2008	DBLP DOI BibTeX RDF
1	Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta	Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.	Algorithmica	2008	DBLP DOI BibTeX RDF	Combinatorial auctions, Hardness of approximation, Social welfare, Submodular
1	Hongda Li, Bao Li	Existence of 3-round zero-knowledge proof systems for NP.	Science in China Series F: Information Sciences	2008	DBLP DOI BibTeX RDF	non-black-box simulation, DDH assumption, zero-knowledge proof, interactive proof
1	Daniel Díaz-Pernil, Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Agustin Riscos-Núñez	A Linear-time Tissue P System Based Solution for the 3-coloring Problem.	Electr. Notes Theor. Comput. Sci.	2007	DBLP DOI BibTeX RDF
1	Amin Coja-Oghlan, Elchanan Mossel, Dan Vilenchik	A Spectral Approach to Analyzing Belief Propagation for 3-Coloring	CoRR	2007	DBLP BibTeX RDF
1	Xueliang Li, Wenli Zhou	Dynamic 3-Coloring of Claw-free Graphs	CoRR	2007	DBLP BibTeX RDF
1	Michael R. Fellows, Frances A. Rosamond	The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number.	CiE	2007	DBLP DOI BibTeX RDF
1	Michael Benisch, Norman M. Sadeh	Examining DCSP coordination tradeoffs.	AAMAS	2006	DBLP DOI BibTeX RDF	constraint processing, computational complexity, agent systems, cooperative distributed problem solving
1	Irit Dinur, Elchanan Mossel, Oded Regev	Conditional hardness for approximate coloring.	STOC	2006	DBLP DOI BibTeX RDF	graph coloring, hardness of approximation, unique games conjecture
1	John Watrous	Zero-knowledge against quantum attacks.	STOC	2006	DBLP DOI BibTeX RDF	zero-knowledge proof systems, quantum cryptography
1	Kishore Kothapalli, Christian Scheideler, Melih Onus, Christian Schindelhauer	Distributed coloring in O/spl tilde/(/spl radic/(log n)) bit rounds.	IPDPS	2006	DBLP DOI BibTeX RDF
1	Hajo Broersma, Fedor V. Fomin, Jan Kratochvíl, Gerhard J. Woeginger	Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult.	Algorithmica	2006	DBLP DOI BibTeX RDF	Computational complexity, Graph coloring, Planar graph, Graph partitioning, Forbidden subgraph
1	Richard Beigel, David Eppstein	3-coloring in time O(1.3289n).	J. Algorithms	2005	DBLP DOI BibTeX RDF
1	Martin Kochol	3-coloring and 3-clique-ordering of locally connected graphs: .	J. Algorithms	2005	DBLP DOI BibTeX RDF
1	Atsuhiro Nakamoto, Katsuhiro Ota, Mamoru Watanabe	On 3-coloring of plane triangulations.	Ars Comb.	2005	DBLP BibTeX RDF
1	Toni Mancini, Marco Cadoli	Detecting and Breaking Symmetries by Reasoning on Problem Specifications.	SARA	2005	DBLP DOI BibTeX RDF
1	Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta	Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.	WINE	2005	DBLP DOI BibTeX RDF
1	Lukasz Kowalik	Fast 3-Coloring Triangle-Free Planar Graphs.	ESA	2004	DBLP DOI BibTeX RDF
1	Mark N. Ellingham, Herbert Fleischner, Martin Kochol, Emanuel Wenger	Colorability of Planar Graphs with Isolated Nontriangular Faces.	Graphs and Combinatorics	2004	DBLP DOI BibTeX RDF	Eulerian triangulation, Hole graph, 3-Coloring
1	Haixia Jia, Cristopher Moore	How Much Backtracking Does It Take to Color Random Graphs? Rigorous Results on Heavy Tails.	CP	2004	DBLP DOI BibTeX RDF
1	Atsuhiro Nakamoto, Katsuhiro Ota, Mamoru Watanabe	On 3-coloring of plane triangulations.	Electronic Notes in Discrete Mathematics	2002	DBLP DOI BibTeX RDF
1	Dimitris Achlioptas, Cristopher Moore	Almost all graphs with average degree 4 are 3-colorable.	STOC	2002	DBLP DOI BibTeX RDF	threshold phenomena, graph coloring, random graphs
1	Hajo Broersma, Fedor V. Fomin, Jan Kratochvíl, Gerhard J. Woeginger	Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous.	SWAT	2002	DBLP DOI BibTeX RDF	computational complexity, graph coloring, planar graph, graph partitioning, forbidden subgraph
1	Krzysztof Diks, Lukasz Kowalik, Maciej Kurowski	A New 3-Color Criterion for Planar Graphs.	WG	2002	DBLP DOI BibTeX RDF
1	Spyridoula M. Armeni, Dimitris Christodoulakis, Ioannis Kostopoulos, Polychronis D. Kountrias, Yannis C. Stamatiou, Michalis Nik Xenos	An Information Hiding Method Based on Computational Intractable Problems.	Panhellenic Conference on Informatics	2001	DBLP DOI BibTeX RDF
1	Richard Beigel, David Eppstein	3-Coloring in Time O(1.3289^n)	CoRR	2000	DBLP BibTeX RDF
1	David Eppstein	Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction	CoRR	2000	DBLP BibTeX RDF
1	Makoto Yokoo, Katsutoshi Hirayama	The Effect of Nogood Learning in Distributed Constraint Satisfaction.	ICDCS	2000	DBLP DOI BibTeX RDF
1	Katsutoshi Hirayama, Makoto Yokoo	An Approach to Over-constrained Distributed Constraint Satisfaction Problems: Distributed Hierarchical Constraint Satisfaction.	ICMAS	2000	DBLP DOI BibTeX RDF
1	Uriel Feige, Michael Langberg, Kobbi Nissim	On the hardness of approximating N P witnesses.	APPROX	2000	DBLP DOI BibTeX RDF
1	Arturo Núñez, María Cristina Riff Rojas	Evaluating Migration Strategies for an Evolutionary Algorithm Based on the Constraint-Graph that Solves CSP.	ISMIS	2000	DBLP BibTeX RDF
1	Arturo Núñez, María Cristina Riff Rojas	Multiple Populations Guided by the Constraint-Graph for CSP.	IBERAMIA-SBIA	2000	DBLP DOI BibTeX RDF
1	Wenan Zang	Proof of Toft's Conjecture: Every Graph Containing No Fully Odd K4 Is 3-Colorable.	COCOON	1998	DBLP DOI BibTeX RDF
1	Uriel Feige, Joe Kilian	Zero Knowledge and the Chromatic Number. (PDF / PS)	IEEE Conference on Computational Complexity	1996	DBLP DOI BibTeX RDF	approximation algorithms, zero knowledge, chromatic number, probabilistically checkable proofs
1	Andreas Nolte, Rainer Schrader	Simulated Annealing and Its Problems to Color Graphs.	ESA	1996	DBLP DOI BibTeX RDF
1	Richard Beigel, David Eppstein	3-Coloring in time O(1.3446n): A no-MIS Algorithm	Electronic Colloquium on Computational Complexity (ECCC)	1995	DBLP BibTeX RDF
1	Peter Rajcáni	Optimal Parallel 3-Coloring Algorithm for Rooted Trees and its Applications.	Inf. Process. Lett.	1992	DBLP DOI BibTeX RDF
1	Avrim Blum	An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring)	STOC	1989	DBLP DOI BibTeX RDF