New Frontiers for Parameterized Complexity
New Frontiers for Parameterized Complexity
Robert Ganian
(ORCID: 0000-0002-7762-8045)
Disciplines
Computer Sciences (100%)
Keywords
-
Parameterized algorithms,
Integer Linear Programming,
Machine Learning,
Width parameters
The design of efficient algorithms for various computational problems is one of the fundamental parts of computer science. While many important computational problems do not admit efficient algorithms if we consider arbitrary inputs, real-life inputs for such problems often contain a certain hidden structure that can be exploited to solve the problem efficiently. The parameterized complexity paradigm provides the perfect tools and techniques to formalize, quantify and exploit various forms of structure in order to efficiently solve a variety of such difficult problems with runtime guarantees. This paradigm has been applied in many fundamental areas of computer science with great success, but there still are prominent areas of computer science where we lack a thorough understanding of what can be accomplished with it. We propose to carry out a rigorous investigation of the parameterized complexity of fundamental problems in two such high-impact areas: integer linear programming and machine learning. The obtained results will allow the design of efficient algorithms capable of exploiting various natural forms of structure in order to find exact solutions for difficult problems in these two important areas of computer science.
The design of efficient algorithms for various computational problems is one of the fundamental parts of computer science. While many important computational problems do not admit efficient algorithms if we consider arbitrary inputs, real-life inputs for such problems often contain a certain hidden structure that can be exploited to solve the problem efficiently. The parameterized complexity paradigm provides the perfect tools and techniques to formalize, quantify and exploit various forms of structure in order to efficiently solve a variety of such difficult problems with runtime guarantees. We carried out a rigorous investigation of fundamental problems in a number of frontier areas in computer science, prominently including integer programming, artificial intelligence and machine learning. The obtained results include not only novel algorithms with strong performance guarantees and an in-depth understanding of the complexity-theoretic behavior of a range of problems in these areas, but also new general-purpose techniques and tools that we then successfully applied to also deepen our understanding of problems in areas such as graph drawing, computational social choice and graph-theoretic algorithmics. Overall, the project supported 62 research publications in scientific journals and conference proceedings.
Research institution(s)
- Wolfgang Pauli Institut - 100%
Research Output
- 303 Citations
- 126 Publications
- 2 Fundings
Publications
-
2024
Title Slim Tree-Cut Width DOI 10.1007/s00453-024-01241-4 Type Journal Article Author Ganian R Journal Algorithmica -
2024
Title The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width DOI 10.1145/3652514 Type Journal Article Author Ganian R Journal ACM Transactions on Algorithms -
2024
Title The edge labeling of higher order Voronoi diagrams DOI 10.1007/s10898-024-01386-0 Type Journal Article Author Claverol M Journal Journal of Global Optimization -
2024
Title Graphs with at most two moplexes DOI 10.1002/jgt.23102 Type Journal Article Author Dallard C Journal Journal of Graph Theory -
2021
Title A Unifying Framework for Characterizing and Computing Width Measures DOI 10.48550/arxiv.2109.14610 Type Preprint Author Eiben E -
2021
Title Worbel: Aggregating Point Labels into Word Clouds DOI 10.48550/arxiv.2109.04368 Type Preprint Author Bhore S -
2021
Title The Parameterized Complexity of Connected Fair Division DOI 10.24963/ijcai.2021/20 Type Conference Proceeding Abstract Author Deligkas A Pages 139-145 Link Publication -
2021
Title On Strict (Outer-)Confluent Graphs DOI 10.7155/jgaa.00568 Type Journal Article Author Förster H Journal Journal of Graph Algorithms and Applications Pages 481-512 Link Publication -
2021
Title New width parameters for SAT and #SAT DOI 10.1016/j.artint.2021.103460 Type Journal Article Author Ganian R Journal Artificial Intelligence Pages 103460 Link Publication -
2021
Title On Structural Parameterizations of the Edge Disjoint Paths Problem DOI 10.1007/s00453-020-00795-3 Type Journal Article Author Ganian R Journal Algorithmica Pages 1605-1637 Link Publication -
2021
Title Measuring what matters: A hybrid approach to dynamic programming with treewidth DOI 10.1016/j.jcss.2021.04.005 Type Journal Article Author Eiben E Journal Journal of Computer and System Sciences Pages 57-75 Link Publication -
2022
Title Parameterized Algorithms for Queue Layouts DOI 10.7155/jgaa.00597 Type Journal Article Author Bhore S Journal Journal of Graph Algorithms and Applications Pages 335-352 Link Publication -
2022
Title Slim Tree-Cut Width DOI 10.48550/arxiv.2206.15091 Type Preprint Author Ganian R -
2022
Title The Complexity of Temporal Vertex Cover in Small-Degree Graphs DOI 10.1609/aaai.v36i9.21259 Type Journal Article Author Hamm T Journal Proceedings of the AAAI Conference on Artificial Intelligence Pages 10193-10201 Link Publication -
2022
Title The Complexity of Envy-Free Graph Cutting DOI 10.24963/ijcai.2022/34 Type Conference Proceeding Abstract Author Deligkas A Pages 237-243 Link Publication -
2022
Title Hedonic Diversity Games: A Complexity Picture with More than Two Colors DOI 10.1609/aaai.v36i5.20435 Type Journal Article Author Ganian R Journal Proceedings of the AAAI Conference on Artificial Intelligence Pages 5034-5042 Link Publication -
2022
Title How to Find a Good Explanation for Clustering? DOI 10.1609/aaai.v36i4.20306 Type Journal Article Author Bandyapadhyay S Journal Proceedings of the AAAI Conference on Artificial Intelligence Pages 3904-3912 Link Publication -
2022
Title Threshold Treewidth and Hypertree Width DOI 10.48550/arxiv.2210.07040 Type Preprint Author Schidler A -
2022
Title The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width DOI 10.48550/arxiv.2210.06845 Type Preprint Author Ganian R -
2022
Title Threshold Treewidth and Hypertree Width DOI 10.1613/jair.1.13661 Type Journal Article Author Ganian R Journal Journal of Artificial Intelligence Research Pages 1687-1713 Link Publication -
2022
Title Hedonic Diversity Games: A Complexity Picture with More than Two Colors DOI 10.48550/arxiv.2202.09210 Type Preprint Author Ganian R -
2022
Title Sum-of-Products with Default Values: Algorithms and Complexity Results DOI 10.1613/jair.1.12370 Type Journal Article Author Ganian R Journal Journal of Artificial Intelligence Research Pages 535-552 Link Publication -
2022
Title Parameterised Partially-Predrawn Crossing Number DOI 10.48550/arxiv.2202.13635 Type Preprint Author Hamm T -
2022
Title The Elekes—Szabó problem and the Uniformity Conjecture DOI 10.1007/s11856-022-2291-9 Type Journal Article Author Makhul M Journal Israel Journal of Mathematics Pages 39-66 -
2022
Title Parameterized Algorithms for Upward Planarity DOI 10.48550/arxiv.2203.05364 Type Preprint Author Chaplick S -
2022
Title An efficient algorithm for counting Markov equivalent DAGs DOI 10.1016/j.artint.2021.103648 Type Journal Article Author Ganian R Journal Artificial Intelligence Pages 103648 -
2018
Title Counting Linear Extensions: Parameterizations by Treewidth DOI 10.1007/s00453-018-0496-4 Type Journal Article Author Eiben E Journal Algorithmica Pages 1657-1683 Link Publication -
2018
Title Parameterized Complexity of Asynchronous Border Minimization DOI 10.1007/s00453-018-0442-5 Type Journal Article Author Ganian R Journal Algorithmica Pages 201-223 -
2021
Title Crossing-Optimal Extension of Simple Drawings DOI 10.4230/lipics.icalp.2021.72 Type Conference Proceeding Abstract Author Ganian R Conference LIPIcs, Volume 198, ICALP 2021 Pages 72:1 - 72:17 Link Publication -
2021
Title Graphs with Two Moplexes ? ? This research was funded in part by the Slovenian Research Agency (I0-0035, research programs P1-0285, P1-0383 and research projects J1-1692, J1-9110, J1-9187, N1-0102, and N1-0160). The authors gratefully acknowledge the DOI 10.1016/j.procs.2021.11.031 Type Journal Article Author Dallard C Journal Procedia Computer Science Pages 248-256 Link Publication -
2021
Title How to Find a Good Explanation for Clustering? DOI 10.48550/arxiv.2112.06580 Type Preprint Author Bandyapadhyay S -
2021
Title Computing Kemeny Rankings from d-Euclidean Preferences DOI 10.1007/978-3-030-87756-9_10 Type Book Chapter Author Hamm T Publisher Springer Nature Pages 147-161 -
2021
Title Worbel DOI 10.1145/3474717.3483959 Type Conference Proceeding Abstract Author Bhore S Pages 256-267 Link Publication -
2021
Title The Complexity of Object Association in Multiple Object Tracking DOI 10.1609/aaai.v35i2.16228 Type Journal Article Author Ganian R Journal Proceedings of the AAAI Conference on Artificial Intelligence Pages 1388-1396 Link Publication -
2022
Title Algorithmic Applications of Tree-Cut Width DOI 10.1137/20m137478x Type Journal Article Author Ganian R Journal SIAM Journal on Discrete Mathematics Pages 2635-2666 Link Publication -
2022
Title Group Activity Selection with Few Agent Types DOI 10.1007/s00453-022-01058-z Type Journal Article Author Ganian R Journal Algorithmica Pages 1111-1155 -
2022
Title Lossy Kernelization of Same-Size Clustering Type Conference Proceeding Abstract Author Bandyapadhyay S Conference Computer Science - Theory and Applications: 17th International Computer Science Symposium in Russia Pages 96-114 -
2022
Title The Complexity of k-Means Clustering when Little is Known Type Conference Proceeding Abstract Author Ganian R Conference Proceedings of the 39th International Conference on Machine Learning Pages 6960-6987 Link Publication -
2021
Title FPT Approximation for Fair Minimum-Load Clustering DOI 10.48550/arxiv.2107.09481 Type Preprint Author Bandyapadhyay S -
2021
Title The complexity landscape of decompositional parameters for ILP: Programs with few global variables and constraints DOI 10.1016/j.artint.2021.103561 Type Journal Article Author Dvorák P Journal Artificial Intelligence Pages 103561 Link Publication -
2021
Title Graphs with at most two moplexes DOI 10.48550/arxiv.2106.10049 Type Preprint Author Dallard C -
2020
Title Using decomposition-parameters for QBF: Mind the prefix! DOI 10.1016/j.jcss.2019.12.005 Type Journal Article Author Eiben E Journal Journal of Computer and System Sciences Pages 1-21 Link Publication -
2020
Title An efficient algorithm for counting markov equivalent DAGs Type Other Author Ganian R. Pages 10136-10143 -
2020
Title Threshold treewidth and hypertree width Type Other Author Ganian R. Pages 1898-1904 -
2020
Title Parameterized Algorithms for Queue Layouts Type Conference Proceeding Abstract Author Bhore S Conference Graph Drawing and Network Visualization - 28th International Symposium, GD 2020 Pages 40-54 -
2020
Title The Complexity Landscape of Resource-Constrained Scheduling Type Conference Proceeding Abstract Author Ganian R Conference Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020 Pages 1741-1747 -
2018
Title The Power of Cut-Based Parameters for Computing Edge Disjoint Paths DOI 10.48550/arxiv.1808.03496 Type Preprint Author Ganian R -
2018
Title Group Activity Selection with Few Agent Types DOI 10.48550/arxiv.1808.06954 Type Preprint Author Ganian R -
2018
Title Sum-of-Products with Default Values: Algorithms and Complexity Results DOI 10.1109/ictai.2018.00115 Type Conference Proceeding Abstract Author Ganian R Pages 733-737 -
2020
Title Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP DOI 10.24963/ijcai.2020/21 Type Conference Proceeding Abstract Author Chen J Pages 146-152 Link Publication -
2020
Title Threshold Treewidth and Hypertree Width DOI 10.24963/ijcai.2020/263 Type Conference Proceeding Abstract Author Ganian R Pages 1898-1904 Link Publication -
2020
Title Extending Partial 1-Planar Drawings DOI 10.48550/arxiv.2004.12222 Type Preprint Author Eiben E -
2020
Title Parameterized Algorithms for Book Embedding Problems DOI 10.7155/jgaa.00526 Type Journal Article Author Bhore S Journal Journal of Graph Algorithms and Applications Pages 603-620 Link Publication -
2020
Title Parameterized Algorithms for Queue Layouts DOI 10.1007/978-3-030-68766-3_4 Type Book Chapter Author Bhore S Publisher Springer Nature Pages 40-54 -
2020
Title Integer Programming and Incidence Treedepth DOI 10.48550/arxiv.2012.00079 Type Preprint Author Eiben E -
2020
Title Crossing-Optimal Extension of Simple Drawings DOI 10.48550/arxiv.2012.07457 Type Preprint Author Ganian R -
2019
Title Shrub-depth: Capturing Height of Dense Graphs DOI 10.23638/lmcs-15(1:7)2019 Type Journal Article Author Ganian R Journal Logical Methods in Computer Science Link Publication -
2023
Title Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension DOI 10.48550/arxiv.2305.06974 Type Preprint Author Bartier V Link Publication -
2023
Title Worbel: Aggregating Point Labels into Word Clouds DOI 10.1145/3603376 Type Journal Article Author Bhore S Journal ACM Transactions on Spatial Algorithms and Systems -
2022
Title On maximum-sum matchings of points DOI 10.60692/d1h2y-bgg09 Type Other Author Oscar Chacón-Rivera Link Publication -
2022
Title On maximum-sum matchings of points DOI 10.60692/pztt3-33905 Type Other Author Oscar Chacón-Rivera Link Publication -
2022
Title The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width DOI 10.4230/lipics.icalp.2022.66 Type Conference Proceeding Abstract Author Ganian R Conference LIPIcs, Volume 229, ICALP 2022 Pages 66:1 - 66:20 Link Publication -
2022
Title A Unifying Framework for Characterizing and Computing Width Measures DOI 10.4230/lipics.itcs.2022.63 Type Conference Proceeding Abstract Author Eiben E Conference LIPIcs, Volume 215, ITCS 2022 Pages 63:1 - 63:23 Link Publication -
2022
Title FPT Approximation for Fair Minimum-Load Clustering DOI 10.4230/lipics.ipec.2022.4 Type Conference Proceeding Abstract Author Bandyapadhyay S Conference LIPIcs, Volume 249, IPEC 2022 Pages 4:1 - 4:14 Link Publication -
2022
Title Slim Tree-Cut Width DOI 10.4230/lipics.ipec.2022.15 Type Conference Proceeding Abstract Author Ganian R Conference LIPIcs, Volume 249, IPEC 2022 Pages 15:1 - 15:18 Link Publication -
2022
Title Parameterised Partially-Predrawn Crossing Number DOI 10.4230/lipics.socg.2022.46 Type Conference Proceeding Abstract Author Hamm T Conference LIPIcs, Volume 224, SoCG 2022 Pages 46:1 - 46:15 Link Publication -
2022
Title Parameterized Algorithms for Upward Planarity DOI 10.4230/lipics.socg.2022.26 Type Conference Proceeding Abstract Author Chaplick S Conference LIPIcs, Volume 224, SoCG 2022 Pages 26:1 - 26:16 Link Publication -
2022
Title Algorithmic Advances via Graph Decomposition Type PhD Thesis Author Thekla Hamm -
2021
Title The Complexity of Bayesian Network Learning: Revisiting the Superstructure Type Other Author Ganian R. Pages 430-442 -
2021
Title Computing Kemeny Rankings from d-Euclidean Preferences Type Conference Proceeding Abstract Author Hamm T Conference Algorithmic Decision Theory - 7th International Conference, ADT 2021 Pages 147-161 -
2021
Title The Power of Cut-Based Parameters for Computing Edge-Disjoint Paths Type Journal Article Author Ganian R Journal Algorithmica Pages 1605-1637 -
2019
Title Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth DOI 10.4230/lipics.mfcs.2019.42 Type Conference Proceeding Abstract Author Eiben E Conference LIPIcs, Volume 138, MFCS 2019 Pages 42:1 - 42:15 Link Publication -
2019
Title Group Activity Selection with Few Agent Types DOI 10.4230/lipics.esa.2019.48 Type Conference Proceeding Abstract Author Ganian R Conference LIPIcs, Volume 144, ESA 2019 Pages 48:1 - 48:16 Link Publication -
2019
Title SAT-Encodings for Treecut Width and Treedepth; In: 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX) DOI 10.1137/1.9781611975499.10 Type Book Chapter Publisher Society for Industrial and Applied Mathematics -
2019
Title Measuring and Exploiting Structure to Solve Hard Problems Type Postdoctoral Thesis Author Robert Ganian -
2023
Title Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results DOI 10.48550/arxiv.2306.03640 Type Preprint Author Focke J Link Publication -
2023
Title How to find a good explanation for clustering? DOI 10.1016/j.artint.2023.103948 Type Journal Article Author Bandyapadhyay S Journal Artificial Intelligence -
2023
Title Parameterized complexity of envy-free resource allocation in social networks DOI 10.1016/j.artint.2022.103826 Type Journal Article Author Eiben E Journal Artificial Intelligence -
2023
Title Hedonic diversity games: A complexity picture with more than two colors DOI 10.1016/j.artint.2023.104017 Type Journal Article Author Ganian R Journal Artificial Intelligence -
2019
Title Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey DOI 10.3390/a12120248 Type Journal Article Author Ganian R Journal Algorithms Pages 248 Link Publication -
2019
Title The Parameterized Complexity of Clustering Incomplete Data DOI 10.48550/arxiv.1911.01465 Type Preprint Author Eiben E -
2019
Title A Join-Based Hybrid Parameter for Constraint Satisfaction DOI 10.1007/978-3-030-30048-7_12 Type Book Chapter Author Ganian R Publisher Springer Nature Pages 195-212 -
2019
Title The Power of Cut-Based Parameters for Computing Edge Disjoint Paths DOI 10.1007/978-3-030-30786-8_15 Type Book Chapter Author Ganian R Publisher Springer Nature Pages 190-204 -
2019
Title Solving Integer Quadratic Programming via Explicit and Structural Restrictions DOI 10.1609/aaai.v33i01.33011477 Type Journal Article Author Eiben E Journal Proceedings of the AAAI Conference on Artificial Intelligence Pages 1477-1484 Link Publication -
2019
Title Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth DOI 10.48550/arxiv.1908.10132 Type Preprint Author Eiben E -
2019
Title Parameterized Algorithms for Book Embedding Problems DOI 10.48550/arxiv.1908.08911 Type Preprint Author Bhore S -
2018
Title On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem DOI 10.4230/lipics.stacs.2018.33 Type Conference Proceeding Abstract Author Ganian R Conference LIPIcs, Volume 96, STACS 2018 Pages 33:1 - 33:14 Link Publication -
0
DOI 10.1145/3474717 Type Other -
2023
Title The Complexity of Envy-Free Graph Cutting DOI 10.48550/arxiv.2312.07043 Type Preprint Author Deligkas A Link Publication -
2022
Title On Covering Segments with Unit Intervals DOI 10.1137/20m1336412 Type Journal Article Author Bergren D Journal SIAM Journal on Discrete Mathematics Pages 1200-1230 Link Publication -
2022
Title On maximum-sum matchings of points DOI 10.1007/s10898-022-01199-z Type Journal Article Author Bereg S Journal Journal of Global Optimization Pages 111-128 Link Publication -
2022
Title Algorithmic Applications of Tree-Cut Width DOI 10.48550/arxiv.2206.00752 Type Preprint Author Ganian R -
2022
Title Weighted Model Counting with Twin-Width DOI 10.48550/arxiv.2206.01706 Type Preprint Author Ganian R -
2022
Title Weighted Model Counting with Twin-Width DOI 10.4230/lipics.sat.2022.15 Type Conference Proceeding Abstract Author Ganian R Conference LIPIcs, Volume 236, SAT 2022 Pages 15:1 - 15:17 Link Publication -
2019
Title A Join-Based Hybrid Parameter for Constraint Satisfaction Type Conference Proceeding Abstract Author Ganian R Conference Proceedings of CP 2019, the 25th International Conference on Principles and Practice of Constraint Programming Pages 195-212 -
2019
Title Finding Linear Arrangements of Hypergraphs with Bounded Cutwidth in Linear Time Type Conference Proceeding Abstract Author Hamm T Conference 14th International Symposium on Parameterized and Exact Computation, IPEC 2019 Pages 20:1-20:14 -
2019
Title Shrub-Depth: Capturing Height of Dense Graphs Type Journal Article Author Ganian R Journal Logical Methods in Computer Science -
2019
Title The Power of Cut-Based Parameters for Computing Edge Disjoint Paths Type Conference Proceeding Abstract Author Ganian R Conference Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019 Pages 190-204 -
2019
Title Integer Programming and Incidence Treedepth Type Conference Proceeding Abstract Author Eiben E Conference Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019 Pages 194-204 -
2019
Title Parameterized Algorithms for Book Embedding Problems Type Conference Proceeding Abstract Author Bhore S Conference Graph Drawing and Network Visualization - 27th International Symposium, GD 2019 Pages 365-378 -
2019
Title The parameterized complexity of cascading portfolio scheduling Type Other Author Eiben E. Pages - -
2019
Title Integer Programming and Incidence Treedepth DOI 10.1007/978-3-030-17953-3_15 Type Book Chapter Author Eiben E Publisher Springer Nature Pages 194-204 -
2019
Title On Strict (Outer-)Confluent Graphs DOI 10.48550/arxiv.1908.05345 Type Preprint Author Förster H -
2019
Title A Join-Based Hybrid Parameter for Constraint Satisfaction DOI 10.48550/arxiv.1907.12335 Type Preprint Author Ganian R -
2019
Title On the Complexity Landscape of Connected f-Factor Problems DOI 10.1007/s00453-019-00546-z Type Journal Article Author Ganian R Journal Algorithmica Pages 2606-2632 -
2019
Title Total generalized variation regularization for multi-modal electron tomography DOI 10.1039/c8nr09058k Type Journal Article Author Huber R Journal Nanoscale Pages 5617-5632 Link Publication -
2019
Title On Maximum-Sum Matchings of Points DOI 10.48550/arxiv.1911.10610 Type Preprint Author Bereg S -
2019
Title SAT-Encodings for Treecut Width and Treedepth DOI 10.48550/arxiv.1911.12995 Type Preprint Author Ganian R -
2019
Title On Strict (Outer-)Confluent Graphs DOI 10.1007/978-3-030-35802-0_12 Type Book Chapter Author Förster H Publisher Springer Nature Pages 147-161 -
2019
Title Parameterized Algorithms for Book Embedding Problems DOI 10.1007/978-3-030-35802-0_28 Type Book Chapter Author Bhore S Publisher Springer Nature Pages 365-378 -
2021
Title The Parameterized Complexity of Clustering Incomplete Data DOI 10.1609/aaai.v35i8.16896 Type Journal Article Author Eiben E Journal Proceedings of the AAAI Conference on Artificial Intelligence Pages 7296-7304 Link Publication -
2020
Title Extending Nearly Complete 1-Planar Drawings in Polynomial Time DOI 10.4230/lipics.mfcs.2020.31 Type Conference Proceeding Abstract Author Eiben E Conference LIPIcs, Volume 170, MFCS 2020 Pages 31:1 - 31:16 Link Publication -
2020
Title Extending Partial 1-Planar Drawings DOI 10.4230/lipics.icalp.2020.43 Type Conference Proceeding Abstract Author Eiben E Conference LIPIcs, Volume 168, ICALP 2020 Pages 43:1 - 43:19 Link Publication -
2020
Title The Complexity Landscape of Resource-Constrained Scheduling DOI 10.24963/ijcai.2020/241 Type Conference Proceeding Abstract Author Ganian R Pages 1741-1747 -
2020
Title On Covering Segments with Unit Intervals DOI 10.4230/lipics.stacs.2020.13 Type Conference Proceeding Abstract Author Bergren D Conference LIPIcs, Volume 154, STACS 2020 Pages 13:1 - 13:17 Link Publication -
2020
Title Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP DOI 10.48550/arxiv.2001.10087 Type Preprint Author Chen J -
2020
Title On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem DOI 10.1007/s00453-020-00758-8 Type Journal Article Author Ganian R Journal Algorithmica Pages 297-336 Link Publication -
2020
Title Parameterized Algorithms for Queue Layouts DOI 10.48550/arxiv.2008.08288 Type Preprint Author Bhore S -
2020
Title Fixed-Parameter Tractability of Dependency QBF with Structural Parameters DOI 10.24963/kr.2020/40 Type Conference Proceeding Abstract Author Ganian R Pages 392-402 Link Publication -
2020
Title Towards a Polynomial Kernel for Directed Feedback Vertex Set DOI 10.1007/s00453-020-00777-5 Type Journal Article Author Bergougnoux B Journal Algorithmica Pages 1201-1221 Link Publication -
2020
Title On Existential MSO and Its Relation to ETH DOI 10.1145/3417759 Type Journal Article Author Ganian R Journal ACM Transactions on Computation Theory (TOCT) Pages 1-32 Link Publication -
2020
Title The Power of Cut-Based Parameters for Computing Edge-Disjoint Paths DOI 10.1007/s00453-020-00772-w Type Journal Article Author Ganian R Journal Algorithmica Pages 726-752 Link Publication -
2020
Title On the Parameterized Complexity of Clustering Incomplete Data into Subspaces of Small Rank DOI 10.1609/aaai.v34i04.5804 Type Journal Article Author Ganian R Journal Proceedings of the AAAI Conference on Artificial Intelligence Pages 3906-3913 Link Publication -
2020
Title Parameterized Complexity of Envy-Free Resource Allocation in Social Networks DOI 10.1609/aaai.v34i05.6201 Type Journal Article Author Eiben E Journal Proceedings of the AAAI Conference on Artificial Intelligence Pages 7135-7142 Link Publication -
2020
Title Title DOI 10.1609/aaai.v34i06.6573 Type Journal Article Author Ganian R Journal Proceedings of the AAAI Conference on Artificial Intelligence Pages 10136-10143 Link Publication -
2020
Title Extending Nearly Complete 1-Planar Drawings in Polynomial Time DOI 10.48550/arxiv.2007.05346 Type Preprint Author Eiben E
Fundings
-
2021
Title Parameterized Analysis in Artificial Intelligence Type Other Start of Funding 2021 Funder Austrian Science Fund (FWF) -
2021
Title Structural Approaches in Stability Under Diversity Constraints Type Travel/small personal Start of Funding 2021 Funder Austrian Agency for International Cooperation in Education and Research