Search results for "edge-coloring"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
88	Uriel Feige, Mohit Singh	Edge Coloring and Decompositions of Weighted Graphs.	ESA	2008	DBLP DOI BibTeX RDF
87	Chun-Chen Hsu, Pangfeng Liu, Da-Wei Wang 0004, Jan-Jan Wu	Generalized Edge Coloring for Channel Assignment in Wireless Networks.	ICPP	2006	DBLP DOI BibTeX RDF
70	Chang-Wu Yu 0001	On the Complexity of the Max-Edge-Coloring Problem with Its Variants.	ESCAPE	2007	DBLP DOI BibTeX RDF	multi-graphs, bipartite graphs, algorithm design, edge coloring
70	Xiao Zhou 0001, Takao Nishizeki	Algorithm for the Cost Edge-Coloring of Trees.	J. Comb. Optim.	2004	DBLP DOI BibTeX RDF	cost edge-coloring, tree, matching, bipartite graph
69	Mathieu Bouchard, Alain Hertz, Guy Desaulniers	Lower bounds and a tabu search algorithm for the minimum deficiency problem.	J. Comb. Optim.	2009	DBLP DOI BibTeX RDF	Minimum deficiency problem, Tabu search, Edge coloring
66	José R. Correa, Michel X. Goemans	An approximate König's theorem for edge-coloring weighted bipartite graphs.	STOC	2004	DBLP DOI BibTeX RDF	bipartite edge coloring, rearrangeability of 3-stage clos networks, bin packing
66	Shin-Ichi Nakano, Xiao Zhou 0001, Takao Nishizeki	Edge-Coloring Algorithms.	Computer Science Today	1995	DBLP DOI BibTeX RDF
63	Guizhen Liu, Changqing Xu	Some Topics on Edge-Coloring.	CJCDGCGT	2005	DBLP DOI BibTeX RDF
62	Iyad A. Kanj, Andreas Wiese, Fenghui Zhang	Local Algorithms for Edge Colorings in UDGs.	WG	2009	DBLP DOI BibTeX RDF
60	Richard Cole 0001, Lukasz Kowalik	New Linear-Time Algorithms for Edge-Coloring Planar Graphs.	Algorithmica	2008	DBLP DOI BibTeX RDF	Algorithm, Planar graph, Edge-coloring, Linear-time
59	Peter Sanders 0001, David Steurer	An asymptotic approximation scheme for multigraph edge coloring.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	chromatic index, data migration, Edge coloring, multigraphs
59	Daniel Kobler, Udi Rotics	Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract).	SODA	2001	DBLP BibTeX RDF	coloring, dominating set, polynomial algorithms, edge-coloring, clique-width, edge-dominating set
56	Huimin Song, Jianliang Wu, Guizhen Liu	The Equitable Edge-Coloring of Series-Parallel Graphs.	International Conference on Computational Science (3)	2007	DBLP DOI BibTeX RDF	equitable, edge-coloring, series-parallel graph
56	Madhav V. Marathe, Alessandro Panconesi, Larry D. Risinger Jr.	An experimental study of a simple, distributed edge-coloring algorithm.	ACM J. Exp. Algorithmics	2004	DBLP DOI BibTeX RDF	experimental analysis of algorithms, scheduling, Distributed algorithms, high performance computing, randomized algorithms, edge coloring
55	Gruia Calinescu, Michael J. Pelsmajer	Fast Edge Colorings with Fixed Number of Colors to Minimize Imbalance.	FSTTCS	2006	DBLP DOI BibTeX RDF
54	Takehiro Ito, Marcin Kaminski 0001, Erik D. Demaine	Reconfiguration of List Edge-Colorings in a Graph.	WADS	2009	DBLP DOI BibTeX RDF
53	Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, Rodica Mihai	Comparing First-Fit and Next-Fit for Online Edge Coloring.	ISAAC	2008	DBLP DOI BibTeX RDF
52	Xiao Zhou 0001, Takao Nishizeki	Edge-Coloring and f-Coloring for Various Classes of Graphs.	ISAAC	1994	DBLP DOI BibTeX RDF
49	David Eppstein	Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.	SODA	2001	DBLP BibTeX RDF
49	Noga Alon, Vera Asodi	Edge Coloring with Delays.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
49	Xiao Zhou 0001, Takao Nishizeki	Algorithm for the Cost Edge-Coloring of Trees.	COCOON	2001	DBLP DOI BibTeX RDF
49	Partha Dutta, Sharad Jaiswal, Debmalya Panigrahi, Rajeev Rastogi	A New Channel Assignment Mechanism for Rural Wireless Mesh Networks.	INFOCOM	2008	DBLP DOI BibTeX RDF
49	Takehiro Ito, Akira Kato, Xiao Zhou 0001, Takao Nishizeki	Algorithms for Finding Distance-Edge-Colorings of Graphs.	COCOON	2005	DBLP DOI BibTeX RDF
46	Gianluca De Marco, Andrzej Pelc	Fast distributed graph coloring with O(Delta) colors.	SODA	2001	DBLP BibTeX RDF
46	Jon Lee 0001, Janny Leung, Sven de Vries	Separating Type-I Odd-Cycle Inequalities for a Binary-Encoded Edge-Coloring Formulation.	J. Comb. Optim.	2005	DBLP DOI BibTeX RDF	odd cycle, integer program, separation, edge coloring, binary encoding
45	Noga Alon, Ayal Zaks	Algorithmic Aspects of Acyclic Edge Colorings.	Algorithmica	2002	DBLP DOI BibTeX RDF	Acyclic edge coloring, Girth
45	Wolfgang Slany	The Complexity of Graph Ramsey Games.	Computers and Games	2000	DBLP DOI BibTeX RDF	combinatorial games, graph Ramsey theory, Ramsey game, winning strategy, achievement game, avoidance game, the game of Sim, endgames, complexity, Java applet, edge coloring, PSPACE-completeness
45	Arthur L. Liestman, Dana S. Richards	Network Communication in Edge-Colored Graphs: Gossiping.	IEEE Trans. Parallel Distributed Syst.	1993	DBLP DOI BibTeX RDF	scheduling communications, scheduling, multiprocessor interconnection networks, gossiping, network communication, graph colouring, edge-colored graphs
42	Martin Marciniszyn, Jozef Skokan, Reto Spöhel, Angelika Steger	Threshold Functions for Asymmetric Ramsey Properties Involving Cliques.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
42	Xiao Zhou 0001, K. Fuse, Takao Nishizeki	A Linear Algorithm for Finding [{g, f}]-Colorings of Partial {k}-Trees.	Algorithmica	2000	DBLP DOI BibTeX RDF
42	Gagan Aggarwal, Rajeev Motwani 0001, Devavrat Shah, An Zhu	Switch Scheduling via Randomized Edge Coloring.	FOCS	2003	DBLP DOI BibTeX RDF
41	Dániel Marx	The complexity of chromatic strength and chromatic edge strength.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	68Q17, Subject classification
41	Shashidhar Gandham, Milind Dawande, Ravi Prakash 0001	Link scheduling in sensor networks: distributed edge coloring revisited.	INFOCOM	2005	DBLP DOI BibTeX RDF
41	Leiming Xu, Yong Xiang, Meilin Shi	A novel channel assignment algorithm based on topology simplification in multi-radio wirelesss mesh networks.	IPCCC	2006	DBLP DOI BibTeX RDF
39	Wangsen Feng, Li'ang Zhang, Wanling Qu, Hanpin Wang	Approximation Algorithms for Maximum Edge Coloring Problem.	TAMC	2007	DBLP DOI BibTeX RDF
39	Ioannis Caragiannis, Afonso Ferreira, Christos Kaklamanis, Stephane Perennes, Pino Persiano, Hervé Rivano	Approximate Constrained Bipartite Edge Coloring.	WG	2001	DBLP DOI BibTeX RDF
39	André C. Pinho, Alexandre A. Santos, Daniel R. Figueiredo 0001, Felipe M. G. França	Two ID-Free Distributed Distance-2 Edge Coloring Algorithms for WSNs.	Networking	2009	DBLP DOI BibTeX RDF	distance-2, WSN, algorithms, MAC
39	Peter Sanders 0001, David Steurer	An asymptotic approximation scheme for multigraph edge coloring.	SODA	2005	DBLP BibTeX RDF
39	Chang-Sung Jeong, Sung-Up Cho, Sun-Chul Whang, Mi-Young Choi	Parallel Edge Coloring of a Tree on a Mesh Connected Computer.	IFIP TCS	2000	DBLP DOI BibTeX RDF
38	Shing-Tsaan Huang, Chi-Hung Tzeng	Distributed edge coloration for bipartite networks.	Distributed Comput.	2009	DBLP DOI BibTeX RDF	Fault-tolerance, Distributed system, Self-stabilization, Edge coloring
38	Xia Zhang, Guizhen Liu	A Class of Graphs of f -Class 1.	International Conference on Computational Science (3)	2007	DBLP DOI BibTeX RDF	simple graph, f-coloring, f-chromatic index, Edge-coloring
35	Xuechao Li, Rong Luo	Edge Coloring of Embedded Graphs with Large Girth.	Graphs Comb.	2003	DBLP DOI BibTeX RDF	Edge chromatic number, Euler contribution, Edge coloring
35	Xuzhen Xie, Mutsunori Yagiura, Takao Ono, Tomio Hirata, Uri Zwick	New Bounds for the Nearly Equitable Edge Coloring Problem.	ISAAC	2007	DBLP DOI BibTeX RDF
35	Christopher L. Barrett, V. S. Anil Kumar 0001, Madhav V. Marathe, Shripad Thite, Gabriel Istrate	Strong Edge Coloring for Channel Assignment in Wireless Radio Networks.	PerCom Workshops	2006	DBLP DOI BibTeX RDF
35	Martin Kochol, Nad'a Krivonáková, Silvia Smejová	Approximation Algorithm for Chromatic Index and Edge-Coloring of Multigraphs.	WEA	2005	DBLP DOI BibTeX RDF
35	Hiroshi Tamura, Kaoru Watanabe, Masakazu Sengoku, Shoji Shinoda	On a new edge coloring related to multihop wireless networks.	APCCAS (2)	2002	DBLP DOI BibTeX RDF
35	Madhav V. Marathe, Alessandro Panconesi, Larry D. Risinger Jr.	An experimental study of a simple, distributed edge coloring algorithm.	SPAA	2000	DBLP DOI BibTeX RDF
35	Xiao Zhou 0001, Shin-Ichi Nakano, Takao Nishizeki	A Parallel Algorithm for Edge-Coloring Partial k-Trees.	SWAT	1994	DBLP DOI BibTeX RDF
35	Xiao Zhou 0001, Takao Nishizeki	Algorithms for Finding f-Colorings of Partial k-Trees.	ISAAC	1995	DBLP DOI BibTeX RDF
32	Akiyoshi Shioura, Mutsunori Yagiura	A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions.	COCOON	2009	DBLP DOI BibTeX RDF
32	Hung Q. Ngo 0001, Van H. Vu	Multirate rearrangeable clos networks and a generalized edge coloring problem on bipartite graphs.	SODA	2003	DBLP BibTeX RDF
32	Jérôme Monnot, Vangelis Th. Paschos, Dominique de Werra, Marc Demange, Bruno Escoffier	Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation.	ISAAC	2004	DBLP DOI BibTeX RDF
31	Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano	Edge Coloring of Bipartite Graphs with Constraints.	MFCS	1999	DBLP DOI BibTeX RDF
29	Valentin Borozan, Gerard Jennhwa Chang, Nathann Cohen, Shinya Fujita 0001, Narayanan Narayanan, Reza Naserasr, Petru Valicov	From Edge-Coloring to Strong Edge-Coloring.	Electron. J. Comb.	2015	DBLP DOI BibTeX RDF
29	Weifa Liang, Xiaojun Shen 0002, Qing Hu 0007	Parallel Algorithms for the Edge-Coloring and Edge-Coloring Update Problems.	J. Parallel Distributed Comput.	1996	DBLP DOI BibTeX RDF
28	Magnús M. Halldórsson, Guy Kortsarz, Maxim Sviridenko	Min Sum Edge Coloring in Multigraphs Via Configuration LP.	IPCO	2008	DBLP DOI BibTeX RDF	Edge Scheduling, Configuration LP, Approximation Algorithms
28	Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos	On the Maximum Edge Coloring Problem.	WAOA	2008	DBLP DOI BibTeX RDF
28	András Gyárfás	Transitive Edge Coloring of Graphs and Dimension of Lattices.	Comb.	2002	DBLP DOI BibTeX RDF	AMS Subject Classification (2000) 05C15
28	Richard Cole 0001, Kirstin Ost, Stefan Schirra	Edge-Coloring Bipartite Multigraphs in O(E log D) Time.	Comb.	2001	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 68W05, 68W40
28	Xiao Zhou 0001, Shin-Ichi Nakano, Takao Nishizeki	A Linear Algorithm for Edge-Coloring Partial k-Trees.	ESA	1993	DBLP DOI BibTeX RDF
28	Harold N. Gabow, San Skulrattanakulchai	Coloring Algorithms on Subcubic Graphs.	COCOON	2002	DBLP DOI BibTeX RDF
27	Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, Zsolt Tuza	Ranking of Graphs.	WG	1994	DBLP DOI BibTeX RDF
25	Nicolas Bourgeois, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos	Approximating the Max Edge-Coloring Problem.	IWOCA	2009	DBLP DOI BibTeX RDF
25	Chadi Kari, Yoo Ah Kim, Seungjoon Lee, Alexander Russell, Minho Shin	Soft Edge Coloring.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
25	Lukasz Kowalik	Improved Edge-Coloring with Three Colors.	WG	2006	DBLP DOI BibTeX RDF
25	Lene M. Favrholdt, Morten N. Nielsen	On-Line Edge-Coloring with a Fixed Number of Colors.	Algorithmica	2003	DBLP DOI BibTeX RDF
25	Andrzej Czygrinow, Michal Hanckowiak, Michal Karonski	Distributed O(Delta log(n))-Edge-Coloring Algorithm.	ESA	2001	DBLP DOI BibTeX RDF
25	Lene M. Favrholdt, Morten N. Nielsen	On-Line Edge-Coloring with a Fixed Number of Colors.	FSTTCS	2000	DBLP DOI BibTeX RDF
25	Christos Kaklamanis, Pino Persiano, Thomas Erlebach, Klaus Jansen	Constrained Bipartite Edge Coloring with Applications to Wavelength Routing.	ICALP	1997	DBLP DOI BibTeX RDF
25	Johannes Schneider 0002, Roger Wattenhofer	A new technique for distributed symmetry breaking.	PODC	2010	DBLP DOI BibTeX RDF	parallel algorithms, coloring, local algorithms, symmetry breaking, network decomposition
24	Fernanda Couto, Diego Amaro Ferraz, Sulamita Klein	New Results on Edge-coloring and Total-coloring of Split Graphs.	CoRR	2023	DBLP DOI BibTeX RDF
24	Leonid Barenboim, Michael Elkin, Tzalik Maimon	Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity.	PODC	2017	DBLP DOI BibTeX RDF
24	Leonid Barenboim, Michael Elkin, Tzalik Maimon	Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity.	CoRR	2016	DBLP BibTeX RDF
24	Csilla Bujtás, E. Sampathkumar 0001, Zsolt Tuza, Charles Dominic, L. Pushpalatha	When the vertex coloring of a graph is an edge coloring of its line graph - a rare coincidence.	Ars Comb.	2016	DBLP BibTeX RDF
24	Henning Bruhn, Richard Lang, Maya Stein	List Edge-Coloring and Total Coloring in Graphs of Low Treewidth.	J. Graph Theory	2016	DBLP DOI BibTeX RDF
24	Shuang-Liang Tian, Ping Chen	Distance Coloring and Distance Edge-Coloring of d- dimensional Lattice.	ICIC (2)	2012	DBLP DOI BibTeX RDF
24	David Eppstein	Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction	CoRR	2000	DBLP BibTeX RDF
24	Xiao Zhou 0001, Takao Nishizeki	Edge-Coloring and f-Coloring for Various Classes of Graphs.	J. Graph Algorithms Appl.	1999	DBLP DOI BibTeX RDF
24	K. McCroan, Robert Christopher Lacher	Region coloring, edge coloring, and scan-conversion of maps.	Int. J. Comput. Geom. Appl.	1994	DBLP DOI BibTeX RDF
24	Hal A. Kierstead	Applications of edge coloring of multigraphs to vertex coloring of graphs.	Discret. Math.	1989	DBLP DOI BibTeX RDF
24	Stefan A. Burr	Some undecidable problems involving the edge-coloring and vertex-coloring of graphs.	Discret. Math.	1984	DBLP DOI BibTeX RDF
21	Thomas Erlebach, Klaus Jansen, Christos Kaklamanis, Giuseppe Persiano	Directed Tree Networks.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Bipartite edge coloring, Approximation algorithms, Optical networks, Path coloring
21	Ming-Jye Lee, Chi-Chang Chen, Chien-Ning Yeh	Permutation Routing in All-Optical Multistage Clos Network.	ITNG	2008	DBLP DOI BibTeX RDF	Optical Crosstalk, Rearrangeable non-blocking, Paull’s Matrix, Edge Coloring, Clos network
21	Marc Demange, Dominique de Werra, Jérôme Monnot, Vangelis Th. Paschos	Time slot scheduling of compatible jobs.	J. Sched.	2007	DBLP DOI BibTeX RDF	Weighted coloring, Chromatic scheduling, Approximations, Edge coloring, Batch scheduling
21	Jihui Wang, Sumei Zhang, Jianfeng Hou	On f -Edge Cover-Coloring of Simple Graphs.	International Conference on Computational Science (3)	2007	DBLP DOI BibTeX RDF	Simple graph, f-edge cover-coloring, Edge-coloring
21	Kazuhiro Suzuki	A Necessary and Sufficient Condition for the Existence of a Heterochromatic Spanning Tree in a Graph.	Graphs Comb.	2006	DBLP DOI BibTeX RDF	Heterochromatic, Spanning tree, Edge-coloring, Rainbow, Multicolored
21	Yongqi Sun, Yuansheng Yang, Feng Xu, Bingxi Li	New Lower Bounds on the Multicolor Ramsey Numbers Rr(C2m).	Graphs Comb.	2006	DBLP DOI BibTeX RDF	Multicolor Ramsey number, Cycle, Edge coloring, Forbidden subgraph
21	Shing-Tsaan Huang, Chi-Hung Tzeng	Distributed Edge Coloration for Bipartite Networks.	SSS	2006	DBLP DOI BibTeX RDF	Fault-tolerance, Distributed system, Self-stabilization, Edge coloring
21	Thomas Erlebach, Stamatis Stefanakos	Wavelength Conversion in All-Optical Networks with Shortest-Path Routing.	Algorithmica	2005	DBLP DOI BibTeX RDF	Wavelength converter placement, Bipartization, Sufficient set, L-reduction, Graph algorithm, Wavelength assignment, Edge coloring
21	Xiao Zhou 0001, Syurei Tamura, Takao Nishizeki	Finding Edge-Disjoint Paths in Partial k-Trees.	Algorithmica	2000	DBLP DOI BibTeX RDF	Polynomial-time algorithm, Edge-coloring, Edge-disjoint paths, Partial k -tree, Bounded treewidth
21	Ravi Jain, Kiran Somalwar, John Werth, James C. Browne	Heuristics for Scheduling I/O Operations.	IEEE Trans. Parallel Distributed Syst.	1997	DBLP DOI BibTeX RDF	Data transfer scheduling, graph edge coloring, I/O bottleneck, multiprocessor operating systems, simultaneous resource scheduling, parallel I/O, scheduling heuristics
21	Xiao Zhou 0001, Syurei Tamura, Takao Nishizeki	Finding Edge-Disjoint Paths in Partial k-Trees (Extended Abstract).	ISAAC	1996	DBLP DOI BibTeX RDF	bounded tree-width, polynomial-time algorithm, edge-coloring, edge-disjoint paths, partial k-tree
21	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
21	Rajeev Motwani 0001, Joseph Naor, Moni Naor	The Probabilistic Method Yields Deterministic Parallel Algorithms	FOCS	1989	DBLP DOI BibTeX RDF	combinatorial constructions, randomized parallel algorithms, deterministic parallel algorithms, set balancing problem, lattice approximation, random sampling, conditional probabilities, probabilistic method, edge-coloring graphs
21	Bonnie Berger, John Rompel	Simulating (log ^c n)-wise Independence in NC	FOCS	1989	DBLP DOI BibTeX RDF	hypergraph coloring problem, randomness removal, (log/sup c/n)-wise independence, randomized NC algorithms, polylogarithmic independence, RNC algorithms, set discrepancy problem, NC edge-coloring algorithm, simulation
21	Marek Kubale	Comments on "Decomposition of Permutation Networks".	IEEE Trans. Computers	1982	DBLP DOI BibTeX RDF	Computer complexity, edge coloring, matrix decomposition
21	David Eppstein, Michael T. Goodrich, Jeremy Yu Meng	Confluent Layered Drawings.	Algorithmica	2007	DBLP DOI BibTeX RDF
21	Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur	Testing Properties of Constraint-Graphs.	CCC	2007	DBLP DOI BibTeX RDF
21	Yossi Chait, C. V. Hollot, Vishal Misra, Donald F. Towsley, Honggang Zhang 0003, Yong Cui	Throughput differentiation using coloring at the network edge and preferential marking at the core.	IEEE/ACM Trans. Netw.	2005	DBLP DOI BibTeX RDF
21	David Eppstein, Michael T. Goodrich, Jeremy Yu Meng	Confluent Layered Drawings.	GD	2004	DBLP DOI BibTeX RDF