Found 161 Documents (Results 1–100)
Polynomial Turing compressions for some graph problems parameterized by modular-width. (English) Zbl 07900289
Wu, Weili (ed.) et al., Computing and combinatorics. 29th international conference, COCOON 2023, Hawaii, HI, USA, December 15–17, 2023. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 14422, 127-140 (2024).
MSC:
68Rxx
A bisection approach to subcubic maximum induced matching. (English) Zbl 07883874
Uehara, Ryuhei (ed.) et al., WALCOM: algorithms and computation. 18th international conference and workshops on algorithms and computation, WALCOM 2024, Kanazawa, Japan, March 18–20, 2024. Proceedings. Singapore: Springer. Lect. Notes Comput. Sci. 14549, 257-272 (2024).
MSC:
68Wxx
Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines. (English) Zbl 07856505
Euclidean TSP in narrow strips. (English) Zbl 07851510
Fair division with minimal withheld information in social networks. (English) Zbl 07811884
MSC:
68Qxx
An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth. (English) Zbl 07807473
MSC:
68Qxx
A parameterized approximation scheme for generalized partial vertex cover. (English) Zbl 07789698
Morin, Pat (ed.) et al., Algorithms and data structures. 18th international symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14079, 93-105 (2023).
Further exploiting \(c\)-closure for FPT algorithms and kernels for domination problems. (English) Zbl 1527.05135
Dynamic coloring on restricted graph classes. (English) Zbl 07745702
Mavronicolas, Marios (ed.), Algorithms and complexity. 13th international conference, CIAC 2023, Larnaca, Cyprus, June 13–16, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13898, 112-126 (2023).
MSC:
68Wxx
Algorithms and complexity of strongly stable non-crossing matchings. (English) Zbl 07728676
Bagchi, Amitabha (ed.) et al., Algorithms and discrete applied mathematics. 9th international conference, CALDAM 2023, Gandhinagar, India, February 9–11, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13947, 363-376 (2023).
MSC:
68Wxx
Algorithms for \(k\)-dispersion for points in convex position in the plane. (English) Zbl 07728653
Bagchi, Amitabha (ed.) et al., Algorithms and discrete applied mathematics. 9th international conference, CALDAM 2023, Gandhinagar, India, February 9–11, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13947, 59-70 (2023).
MSC:
68Wxx
Balanced connected partitions of graphs: approximation, parameterization and lower bounds. (English) Zbl 07721469
Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number. (English) Zbl 07704069
Further exploiting \(c\)-closure for FPT algorithms and kernels for domination problems. (English) Zbl 07836606
Berenbrink, Petra (ed.) et al., 39th international symposium on theoretical aspects of computer science, STACS 2022, Marseille, France, virtual conference, March 15–18, 2022. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 219, Article 39, 20 p. (2022).
MSC:
68Qxx
Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract). (English) Zbl 07682399
Bekos, Michael A. (ed.) et al., Graph-theoretic concepts in computer science. 48th international workshop, WG 2022, Tübingen, Germany, June 22–24, 2022. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13453, 29-42 (2022).
MSC:
68R10
Block-structured integer programming: can we parameterize without the largest coefficient? (English) Zbl 1512.90141
MSC:
90C10
Parameterized algorithms and complexity for the traveling purchaser problem and its variants. (English) Zbl 1504.90139
A general scheme for solving a large set of scheduling problems with rejection in FPT time. (English) Zbl 1489.90027
FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees. (English) Zbl 1507.68323
Reviewer: Krzysztof Gdawiec (Sosnowiec)
An improved deterministic parameterized algorithm for cactus vertex deletion. (English) Zbl 1487.05250
Anonymity-preserving space partitions. (English) Zbl 07788605
Ahn, Hee-Kap (ed.) et al., 32nd international symposium on algorithms and computation, ISAAC 2021, Fukuoka, Japan, December 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 212, Article 32, 16 p. (2021).
MSC:
68Wxx
Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes. (English) Zbl 07530235
Bampis, Evripidis (ed.) et al., Fundamentals of computation theory. 23rd international symposium, FCT 2021, Athens, Greece, September 12–15, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12867, 217-229 (2021).
MSC:
68Qxx
An FPT algorithm for matching cut and d-cut. (English) Zbl 07495046
Flocchini, Paola (ed.) et al., Combinatorial algorithms. 32nd international workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12757, 531-543 (2021).
Minimum eccentricity shortest path problem with respect to structural parameters. (English) Zbl 07495040
Flocchini, Paola (ed.) et al., Combinatorial algorithms. 32nd international workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12757, 442-455 (2021).
Line segment disk cover. (English) Zbl 07412192
Euclidean TSP in narrow strips. (English) Zbl 07760133
Cabello, Sergio (ed.) et al., 36th international symposium on computational geometry, SoCG 2020, Zürich, Switzerland (virtual conference), June 23–26, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 164, Article 4, 16 p. (2020).
MSC:
68U05
Iterated type partitions. (English) Zbl 07601008
Gąsieniec, Leszek (ed.) et al., Combinatorial algorithms. 31st international workshop, IWOCA 2020, Bordeaux, France, June 8–10, 2020, Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12126, 195-210 (2020).
Solving packing problems with few small items using rainbow matchings. (English) Zbl 07559382
Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 11, 14 p. (2020).
MSC:
68Qxx
An optimal algorithm for bisection for bounded-treewidth graph. (English) Zbl 07369998
Li, Minming (ed.), Frontiers in algorithmics. 14th international workshop, FAW 2020, Haikou, China, October 19–21, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12340, 25-36 (2020).
MSC:
68Wxx
A constant FPT approximation algorithm for hard-capacitated \(k\)-means. (English) Zbl 1457.90138
MSC:
90C27
A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number. (English) Zbl 1470.57035
Reviewer: Jason Hanson (Redmond)
Fixed-parameter tractable algorithm and polynomial kernel for Max-Cut Above Spanning Tree. (English) Zbl 1434.68748
Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results. (English) Zbl 1435.68222
Backdoors to planning. (English) Zbl 1478.68323
An improved linear kernel for complementary maximal strip recovery: simpler and smaller. (English) Zbl 1429.68340
The parameterized complexity of cycle packing: indifference is not an issue. (English) Zbl 1429.68195
Gene tree reconciliation including transfers with replacement is NP-hard and FPT. (English) Zbl 1423.92205
On the subnet prune and regraft distance. (English) Zbl 1411.05249
Reviewer: Zhizhang Shen (Plymouth)
Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number. (English) Zbl 1528.68311
Ganguly, Sumit (ed.) et al., 38th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2018, Ahmedabad, India, December 11–13, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 122, Article 35, 19 p. (2018).
Gaifman normal forms for counting extensions of first-order logic. (English) Zbl 1499.03028
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 133, 14 p. (2018).
Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces. (English) Zbl 1489.68345
Speckmann, Bettina (ed.) et al., 34th international symposium on computational geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 99, Article 21, 14 p. (2018).
Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms. (English) Zbl 1443.68121
Lokshtanov, Daniel (ed.) et al., 12th international symposium on parameterized and exact computation, IPEC 2017, Vienna, Austria, September 6–8, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 89, Article 7, 13 p. (2018).
On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width. (English) Zbl 1401.05225
Algorithms for node-weighted Steiner tree and maximum-weight connected subgraph. (English) Zbl 1396.90016
Complexity of minimum irreducible infeasible subsystem covers for flow networks. (English) Zbl 1387.05243
Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials. (English) Zbl 1391.68055
Covering a tree with rooted subtrees – parameterized and approximation algorithms. (English) Zbl 1403.68343
Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 2801-2820 (2018).
Finding detours is fixed-parameter tractable. (English) Zbl 1441.68104
Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 54, 14 p. (2017).
A finitary analogue of the downward Löwenheim-Skolem property. (English) Zbl 1434.03091
Goranko, Valentin (ed.) et al., 26th EACSL annual conference on computer science logic, CSL 2017, Stockholm, Sweden, August 20–24, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 82, Article 37, 21 p. (2017).
A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number. (English) Zbl 1411.68172
Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2721-2732 (2017).
A fast parameterized algorithm for co-path set. (English) Zbl 1398.90197
Guo, Jiong (ed.) et al., 11th international symposium on parameterized and exact computation (IPEC 2016), Aarhus, Denmark, August 24–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-023-1). LIPIcs – Leibniz International Proceedings in Informatics 63, Article 28, 13 p. (2017).
Improved algorithms and combinatorial bounds for independent feedback vertex set. (English) Zbl 1398.68203
Guo, Jiong (ed.) et al., 11th international symposium on parameterized and exact computation (IPEC 2016), Aarhus, Denmark, August 24–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-023-1). LIPIcs – Leibniz International Proceedings in Informatics 63, Article 2, 14 p. (2017).
Possible winner problems on partial tournaments: a parameterized study. (English) Zbl 1371.90123
MSC:
90C27
Parameterized algorithms for min-max multiway cut and list digraph homomorphism. (English) Zbl 1370.68131
Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory. (English) Zbl 1349.90116
Strong parameterized deletion: bipartite graphs. (English) Zbl 1391.68092
Lal, Akash (ed.) et al., 36th IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2016), Chennai, India, December 13–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-027-9). LIPIcs – Leibniz International Proceedings in Informatics 65, Article 21, 14 p. (2016).
Optimal nonpreemptive scheduling in a smart grid model. (English) Zbl 1398.90051
Seok-Hee Hong (ed.), 27th international symposium on algorithms and computation, ISAAC 2016, Sydney, Australia, December 12–14, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-026-2). LIPIcs – Leibniz International Proceedings in Informatics 64, Article 53, 13 p. (2016).
On \(r\)-guarding thin orthogonal polygons. (English) Zbl 1398.68614
Seok-Hee Hong (ed.), 27th international symposium on algorithms and computation, ISAAC 2016, Sydney, Australia, December 12–14, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-026-2). LIPIcs – Leibniz International Proceedings in Informatics 64, Article 17, 13 p. (2016).
On the hardness of learning sparse parities. (English) Zbl 1397.68083
Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 11, 17 p. (2016).
FPT approximation algorithm for scheduling with memory constraints. (English) Zbl 1377.68046
Dutot, Pierre-François (ed.) et al., Euro-Par 2016: parallel processing. 22nd international conference on parallel and distributed computing, Grenoble, France, August 24–26, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-43658-6/pbk; 978-3-319-43659-3/ebook). Lecture Notes in Computer Science 9833, 196-208 (2016).
Parameterized algorithms for non-separating trees and branchings in digraphs. (English) Zbl 1353.68106
Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis. (English) Zbl 1347.68168
On the complexity of submap isomorphism and maximum common submap problems. (English) Zbl 1373.68355
Fixed-parameter tractable distances to sparse graph classes. (English) Zbl 1378.68066
Husfeldt, Thore (ed.) et al., 10th international symposium on parameterized and exact computation, IPEC 2015, Patras, Greece, September 16–18, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-92-7). LIPIcs – Leibniz International Proceedings in Informatics 43, 236-247 (2015).
Parameterized algorithms for MIN-MAX multiway cut and List digraph homomorphism. (English) Zbl 1378.68084
Husfeldt, Thore (ed.) et al., 10th international symposium on parameterized and exact computation, IPEC 2015, Patras, Greece, September 16–18, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-92-7). LIPIcs – Leibniz International Proceedings in Informatics 43, 78-89 (2015).
Roman domination in subgraphs of grids. (English) Zbl 1347.05147
Campêlo, Manoel (ed.) et al., LAGOS ’15. Selected papers of the 8th Latin-American algorithms, graphs, and optimization symposium, Praia das Fontes, Beberibe, Brazil, May 11–15, 2015. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 50, 77-82, electronic only (2015).
Filter Results by …
Document Type
- Journal Articles (115)
- Collection Articles (45)
- Books (1)
all
top 5
Author
- Gutin, Gregory Z. (20)
- Saurabh, Saket (19)
- Yeo, Anders (11)
- Jones, Mark (8)
- Kim, Eun Jung (7)
- Thilikos, Dimitrios M. (6)
- Zehavi, Meirav (6)
- Kim, Eunjung (5)
- Paul, Christophe (5)
- Sau, Ignasi (5)
- Wahlström, Magnus (5)
- Xiao, Mingyu (5)
- Crowston, Robert (4)
- Eppstein, David Arthur (4)
- Kobayashi, Yasuaki (4)
- Lokshtanov, Daniel (4)
- Misra, Pranabendu (4)
- Oum, Sang-Il (4)
- Sharma, Roohani (4)
- Alon, Noga (3)
- Buchanan, Austin (3)
- Bulian, Jannis (3)
- Dawar, Anuj (3)
- Fomin, Fedor V. (3)
- Gutner, Shai (3)
- Krithika, R. (3)
- Madathil, Jayakrishnan (3)
- Mnich, Matthias (3)
- Philip, Geevarghese (3)
- Reidl, Felix (3)
- Sahu, Abhishek (3)
- Szeider, Stefan (3)
- Yang, Yongjie (3)
- Alkema, Henk (2)
- Basappa, Manjanna (2)
- Bezáková, Ivona (2)
- Chen, Jian-er (2)
- Chen, Lin (2)
- Chen, Yijia (2)
- Chimani, Markus (2)
- Curticapean, Radu (2)
- de Berg, Mark Theodoor (2)
- Dell, Holger (2)
- Estivill-Castro, Vladimir (2)
- Fellows, Michael Ralph (2)
- Flum, Jörg (2)
- Golovach, Petr A. (2)
- Hanaka, Tesshu (2)
- Havvaei, Elham (2)
- Heggernes, Pinar (2)
- Hermelin, Danny (2)
- Hliněný, Petr (2)
- Jiang, Haitao (2)
- Kanesh, Lawqueen (2)
- Kisfaludi-Bak, Sándor (2)
- Kratsch, Dieter (2)
- Lin, Weibo (2)
- Liu, Hsiang-Hsuan (2)
- Maria, Clément (2)
- Marx, Dániel (2)
- Meesum, Syed Mohammad (2)
- Meister, Daniel (2)
- Misra, Neeldhara (2)
- Mohar, Bojan (2)
- Mutzel, Petra (2)
- Nagamochi, Hiroshi (2)
- Paulusma, Daniël (2)
- Rai, Ashutosh (2)
- Raman, Venkatesh (2)
- Ramanujan, M. S. (2)
- Rosamond, Frances A. (2)
- Roy, Sanjukta (2)
- Sampaio, Rudini Menezes (2)
- Škoda, Petr (2)
- Soleimanfallah, Arezou (2)
- Spreer, Jonathan (2)
- Stege, Ulrike (2)
- Suchý, Ondřej (2)
- Tale, Prafullkumar (2)
- Thomassé, Stéphan (2)
- Wang, Jianxin (2)
- Whitesides, Sue H. (2)
- Zhu, Binhai (2)
- Agrawal, Akanksha (1)
- Amini, Omid (1)
- Ananth, Prabhanjan Vijendra (1)
- Anders, John (1)
- Angel, Eric (1)
- Aoike, Yuuki (1)
- Aravind, N. R. (1)
- Arvind, Vikraman (1)
- Badanidiyuru, Ashwinkumar (1)
- Bandyapadhyay, Sayan (1)
- Bang-Jensen, Jørgen (1)
- Banik, Aritra (1)
- Bannach, Max (1)
- Bannister, Michael J. (1)
- Bansal, Manish Kumar (1)
- Baste, Julien (1)
- Berndt, Sebastian (1)
- and 212 more Authors
all
top 5
Serial
- Theor. Comput. Sci. (20)
- Algorithmica (15)
- J. Comput. Syst. Sci. (13)
- Discrete Appl. Math. (8)
- Inf. Process. Lett. (8)
- J. Comb. Optim. (6)
- SIAM J. Discrete Math. (4)
- J. Discrete Algorithms (4)
- J. Graph Algorithms Appl. (3)
- Oper. Res. Lett. (2)
- Inf. Comput. (2)
- Int. J. Comput. Geom. Appl. (2)
- Theory Comput. Syst. (2)
- J. Sched. (2)
- Discrete Optim. (2)
- ACM Trans. Algorithms (2)
- Artif. Intell. (1)
- Discrete Math. (1)
- J. Math. Biol. (1)
- Ars Comb. (1)
- J. Math. Psychol. (1)
- J. Symb. Log. (1)
- Math. Oper. Res. (1)
- Networks (1)
- Oper. Res. (1)
- SIAM J. Comput. (1)
- Acta Math. Appl. Sin., Engl. Ser. (1)
- Graphs Comb. (1)
- Discrete Comput. Geom. (1)
- Pattern Recognition (1)
- Electron. J. Comb. (1)
- Discrete Math. Theor. Comput. Sci. (1)
- Optim. Eng. (1)
- Found. Comput. Math. (1)
- Adv. Appl. Discrete Math. (1)
- J. Comput. Geom. (1)
- Texts Theor. Comput. Sci., EATCS Ser. (1)