Solving the list coloring problem through a branch-and-price algorithm. (English) Zbl 07895428
MSC:
90Bxx
Found 86 Documents (Results 1–86)
A faster exponential time algorithm for bin packing with a constant number of bins via additive combinatorics. (English) Zbl 1529.68186
Inapproximability of shortest paths on perfect matching polytopes. (English) Zbl 1534.90173
Del Pia, Alberto (ed.) et al., Integer programming and combinatorial optimization. 24th international conference, IPCO 2023, Madison, WI, USA, June 21–23, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13904, 72-86 (2023).
MSC:
90C35
Using a geometric lens to find \(k\)-disjoint shortest paths. (English) Zbl 1527.05048
Reviewer: K. M. Kathiresan (Sivakasi)
The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals. (English) Zbl 1541.68440
Cai, Zhiping (ed.) et al., Theoretical computer science. 40th national conference, NCTCS 2022, Changchun, China, July 29–31, 2022. Revised selected papers. Singapore: Springer. Commun. Comput. Inf. Sci. 1693, 77-95 (2022).
On the fine-grained parameterized complexity of partial scheduling to minimize the makespan. (English) Zbl 1537.68054
Many-visits TSP revisited. (English) Zbl 1478.68464
On undirected two-commodity integral flow, disjoint paths and strict terminal connection problems. (English) Zbl 1528.90052
The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem. (English) Zbl 1512.90204
Cai, Zhiping (ed.) et al., Theoretical computer science. 39th national conference, NCTCS 2021, Yinchuan, China, July 23–25, 2021. Revised selected papers. Singapore: Springer. Commun. Comput. Inf. Sci. 1494, 177-195 (2021).
MSC:
90C27
On the fine-grained parameterized complexity of partial scheduling to minimize the makespan. (English) Zbl 1537.68055
Cao, Yixin (ed.) et al., 15th international symposium on parameterized and exact computation, IPEC 2020, Hong Kong, China, virtual conference, December 14–18, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 180, Article 25, 17 p. (2020).
Palette sparsification beyond \((\Delta +1)\) vertex coloring. (English) Zbl 07758308
Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 6, 22 p. (2020).
A new genetic algorithm encoding for coalition structure generation problems. (English) Zbl 07346006
Walking through waypoints. (English) Zbl 1436.68218
A branch and price algorithm for list coloring problem. (English) Zbl 07515216
Coutinho, Gabriel (ed.) et al., Proceedings of LAGOS 2019, the tenth Latin and American algorithms, graphs and optimization symposium, Belo Horizonte, Brazil, June 2–7 2019. Amsterdam: Elsevier. Electron. Notes Theor. Comput. Sci. 346, 613-624 (2019).
Special frequency quadrilaterals and an application. (English) Zbl 1456.90139
Sun, Xiaoming (ed.) et al., Theoretical computer science. 37th national conference, NCTCS 2019, Lanzhou, China, August 2–4, 2019. Revised selected papers. Singapore: Springer. Commun. Comput. Inf. Sci. 1069, 16-26 (2019).
A space-efficient parameterized algorithm for the Hamiltonian cycle problem by dynamic algebraization. (English) Zbl 1533.68205
van Bevern, René (ed.) et al., Computer science – theory and applications. 14th international computer science symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1–5, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11532, 38-49 (2019).
Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem. (English) Zbl 1426.90244
A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals. (English) Zbl 1499.05599
An exact algorithm for the Steiner forest problem. (English) Zbl 1524.68242
Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 70, 14 p. (2018).
Isolating a vertex via lattices: polytopes with totally unimodular faces. (English) Zbl 1499.68368
Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 74, 14 p. (2018).
A method to compute the sparse graphs for traveling salesman problem based on frequency quadrilaterals. (English) Zbl 1452.90280
Chen, Jianer (ed.) et al., Frontiers in algorithmics. 12th international workshop, FAW 2018, Guangzhou, China, May 8–10, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10823, 286-299 (2018).
Width, depth, and space: tradeoffs between branching and dynamic programming. (English) Zbl 1461.68147
A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network. (English) Zbl 1402.90139
Parameterized counting matching and packing: a family of hard problems that admit FPTRAS. (English) Zbl 1393.68076
Parameterized complexity of the workflow satisfiability problem. (English) Zbl 1397.90206
Fukunaga, Takuro (ed.) et al., Combinatorial optimization and graph algorithms. Communications of NII Shonan meetings. Singapore: Springer (ISBN 978-981-10-6146-2/hbk; 978-981-10-6147-9/ebook). 101-120 (2017).
MSC:
90B50
Exact and superpolynomial approximation algorithms for the densest K-subgraph problem. (English) Zbl 1375.90296
Strong valid inequalities for Boolean logical pattern generation. (English) Zbl 1408.90184
MSC:
90C09
Parameterized exact and approximation algorithms for maximum \(k\)-set cover and related satisfiability problems. (English) Zbl 1400.68081
Parameterized approximation algorithms for packing problems. (English) Zbl 1355.68294
Reviewer: Vladimír Lacko (Košice)
An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs. (English) Zbl 1354.90104
An approximation algorithm for the longest path problem in solid grid graphs. (English) Zbl 1357.68297
An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure. (English) Zbl 1348.90559
Reviewer: Vladimír Lacko (Košice)
MSC:
90C27
Deterministic algorithms for matching and packing problems based on representative sets. (English) Zbl 1330.68111
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. (English) Zbl 1327.68126
Algorithmic aspects of Steiner convexity and enumeration of Steiner trees. (English) Zbl 1332.90326
MSC:
90C35
Computing and counting longest paths on circular-arc graphs in polynomial time. (English) Zbl 1288.05137
An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure. (English) Zbl 1382.90097
Chan, T-H. Hubert (ed.) et al., Theory and applications of models of computation. 10th international conference, TAMC 2013, Hong Kong, China, May 20–22, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38235-2/pbk). Lecture Notes in Computer Science 7876, 96-107 (2013).
The negative cycles polyhedron and hardness of checking some polyhedral properties. (English) Zbl 1225.90143
Colorings with few colors: counting, enumeration and combinatorial bounds. (English) Zbl 1309.05172
Thilikos, Dimitrios M. (ed.), Graph theoretic concepts in computer science. 36th international workshop, WG 2010, Zarós, Crete, Greece, June 28–30, 2010. Revised papers. Berlin: Springer (ISBN 978-3-642-16925-0/pbk). Lecture Notes in Computer Science 6410, 39-50 (2010).
Dynamic programming based algorithms for set multicover and multiset multicover problems. (English) Zbl 1203.68316
Efficient approximation of combinatorial problems by moderately exponential algorithms. (English) Zbl 1253.68357
Dehne, Frank (ed.) et al., Algorithms and data structures. 11th international symposium, WADS 2009, Banff, Canada, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03366-7/pbk). Lecture Notes in Computer Science 5664, 507-518 (2009).
Approaches to the Steiner problem in networks. (English) Zbl 1248.68069
Lerner, Jürgen (ed.) et al., Algorithmics of large and complex networks. Design, analysis, and simulation. Berlin: Springer (ISBN 978-3-642-02093-3/pbk). Lecture Notes in Computer Science 5515, 81-103 (2009).
Faster Steiner tree computation in polynomial-space. (English) Zbl 1158.68429
Halperin, Dan (ed.) et al., Algorithms – ESA 2008. 16th annual European symposium, Karlsruhe, Germany, September 15–17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-87743-1/pbk). Lecture Notes in Computer Science 5193, 430-441 (2008).
Facility location problems: A parameterized view. (English) Zbl 1143.90354
Fleischer, Rudolf (ed.) et al., Algorithmic aspects in information and management. 4th international conference, AAIM 2008, Shanghai, China, June 23–25, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-68865-5/pbk). Lecture Notes in Computer Science 5034, 188-199 (2008).
MSC:
90B80
Speeding up dynamic programming for some NP-hard graph recoloring problems. (English) Zbl 1139.68394
Agrawal, Manindra (ed.) et al., Theory and applications of models of computation. 5th international conference, TAMC 2008, Xi’an, China, April 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79227-7/pbk). Lecture Notes in Computer Science 4978, 490-501 (2008).
Filter Results by …
Document Type
- Journal Articles (67)
- Collection Articles (19)
all
top 5
Author
- Paschos, Vangelis Th. (6)
- Nederlof, Jesper (4)
- Wang, Yong (4)
- Bourgeois, Nicolas (3)
- Escoffier, Bruno (3)
- Fernau, Henning (3)
- Golovnev, Alexander (3)
- Kratsch, Dieter (3)
- Nagamochi, Hiroshi (3)
- Swennenhuis, Céline M. F. (3)
- Wahlström, Magnus (3)
- Xiao, Mingyu (3)
- Chen, Li-Hsuan (2)
- Cygan, Marek (2)
- Della Croce, Federico (2)
- Fellows, Michael Ralph (2)
- Fomin, Fedor V. (2)
- Fürer, Martin (2)
- Grandoni, Fabrizio (2)
- Gurjar, Rohit (2)
- Gutin, Gregory Z. (2)
- Jansen, Bart M. P. (2)
- Liedloff, Mathieu (2)
- Lucci, Mauro (2)
- Nasini, Graciela L. (2)
- Severin, Daniel E. (2)
- Thierauf, Thomas (2)
- Vishnoi, Nisheeth K. (2)
- Wang, Jianxin (2)
- Zehavi, Meirav (2)
- Akhoondian Amiri, Saeed (1)
- Alon, Noga (1)
- Asgharian-Sardroud, Asghar (1)
- Assadi, Sepehr (1)
- Bagheri, Alireza (1)
- Basso, Franco (1)
- Belbasi, Mahdi (1)
- Bentert, Matthias (1)
- Bentz, Cédric (1)
- Bermond, Jean-Claude (1)
- Bezáková, Ivona (1)
- Binkele-Raible, Daniel (1)
- Bodlaender, Hans L. (1)
- Böhm, Martin (1)
- Bonnet, Edouard (1)
- Borgwardt, Steffen (1)
- Boria, Nicolas (1)
- Boros, Endre (1)
- Bosch, Paul J. (1)
- Brand, Cornelius (1)
- Buchanan, Austin (1)
- Buchheim, Christoph (1)
- Chang, Maw-Shang (1)
- Chateau, Annie (1)
- Chen, Lina (1)
- Contreras, Juan Pablo (1)
- Costa, Marie-Christine (1)
- Coudert, David (1)
- Couturier, Jean-Francois (1)
- Crampton, Jason (1)
- Cui, Lei (1)
- D’Angelo, Gianlorenzo (1)
- de Figueiredo, Celina M. Herrera (1)
- de Kroon, Arnoud A. W. M. (1)
- de Melo, Alexsander A. (1)
- D’Emidio, Mattia (1)
- dos Santos Souza, Uéverton (1)
- Dourado, Mitre Costa (1)
- Elbassioni, Khaled M. (1)
- Elkind, Edith (1)
- Feldmann, Andreas Emil (1)
- Feng, Qilong (1)
- Figueiredo, Celina M. H. (1)
- Forlizzi, Luca (1)
- Förster, Klaus-Tycho (1)
- Frigioni, Daniele (1)
- Fu, Bin (1)
- Gaspers, Serge (1)
- Giannakos, Aristotelis (1)
- Giroudeau, Rodolphe (1)
- Golovach, Petr A. (1)
- Gottschau, Marinus (1)
- Goyal, Prachi (1)
- Gurvich, Vladimir A. (1)
- Henke, Dorothee (1)
- Hertz, Alain (1)
- Hirai, Hiroshi (1)
- Hoeksma, Ruben (1)
- Hommelsheim, Felix (1)
- Hua, Qiangsheng (1)
- Huang, Xiaohui (1)
- Hüffner, Falk (1)
- Hung, Ling-Ju (1)
- Imamiya, Akinori (1)
- Jaffke, Lars (1)
- Jain, Vishesh (1)
- Jennings, Nicholas R. (1)
- Kaiser, Marcus (1)
- König, Jean-Claude (1)
- Koutecký, Martin (1)
- and 95 more Authors
all
top 5
Serial
- Algorithmica (8)
- J. Comb. Optim. (6)
- Discrete Appl. Math. (5)
- Theor. Comput. Sci. (5)
- Inf. Process. Lett. (3)
- J. Comput. Syst. Sci. (3)
- Networks (3)
- SIAM J. Discrete Math. (3)
- Eur. J. Oper. Res. (3)
- SIAM J. Comput. (2)
- Oper. Res. Lett. (2)
- Ann. Oper. Res. (2)
- Theory Comput. Syst. (2)
- J. Discrete Algorithms (2)
- Algorithms (Basel) (2)
- Artif. Intell. (1)
- Oper. Res. (1)
- Optimization (1)
- Inf. Comput. (1)
- Comput. Oper. Res. (1)
- Int. J. Found. Comput. Sci. (1)
- J. Glob. Optim. (1)
- Filomat (1)
- INFORMS J. Comput. (1)
- Math. Probl. Eng. (1)
- Optim. Methods Softw. (1)
- J. Graph Algorithms Appl. (1)
- 4OR (1)
- Discrete Optim. (1)
- RAIRO, Theor. Inform. Appl. (1)
- Adv. Comb. (1)
all
top 3
Software
- CPLEX (2)
- DIMACS (2)
- GitHub (2)
- Leibniz (2)
- SteinLib (2)
- vnep-approx (2)
- Algorithm 447 (1)
- BARON (1)
- BBMCSP (1)
- BBMCW (1)
- Benchmarks for Optimization Software (1)
- CSDP (1)
- ComputeTW (1)
- Concorde (1)
- ElemStatLearn (1)
- GeoSteiner (1)
- Gurobi (1)
- ISLR (1)
- LEMON (1)
- LINDO (1)
- LINGO (1)
- LKH (1)
- MAX-2-SAT (1)
- MCODE (1)
- MaxCliqueDyn (1)
- OEIS (1)
- SCIP (1)
- SNDlib (1)
- Sat4j (1)
- TSPLIB (1)
- UCI-ml (1)
- igraph (1)
- topologyzoo-treewidth-analysis (1)
