Search

Your search keyword '"Fixed-parameter tractability"' showing total 27 results
Start Over Descriptor "Fixed-parameter tractability" Publisher springer international publishing

Refine your results

more »

more »

27 results on '"Fixed-parameter tractability"'

1. On Structural Parameterizations of Node Kayles

Author

Kobayashi, Yasuaki, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Akiyama, Jin, editor, Marcelo, Reginaldo M., editor, Ruiz, Mari-Jo P., editor, and Uno, Yushi, editor

Published
2021
Full Text
View/download PDF

2. On Finding Separators in Temporal Split and Permutation Graphs

Author

Maack, Nicolas, Molter, Hendrik, Niedermeier, Rolf, Renken, Malte, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bampis, Evripidis, editor, and Pagourtzis, Aris, editor

Published
2021
Full Text
View/download PDF

3. How to Catch Marathon Cheaters: New Approximation Algorithms for Tracking Paths

Author

Goodrich, Michael T., Gupta, Siddharth, Khodabandeh, Hadi, Matias, Pedro, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Lubiw, Anna, editor, and Salavatipour, Mohammad, editor

Published
2021
Full Text
View/download PDF

5. Occupancy Number Restricted Boolean Petri Net Synthesis: A Fixed-Parameter Algorithm

Author

Erofeev, Evgeny, Tredup, Ronny, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Pun, Violet Ka I, editor, Stolz, Volker, editor, and Simao, Adenilso, editor

Published
2020
Full Text
View/download PDF

6. Clique-Width of Point Configurations

Author

Çağırıcı, Onur, Hliněný, Petr, Pokrývka, Filip, Sankaran, Abhisekh, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Adler, Isolde, editor, and Müller, Haiko, editor

Published
2020
Full Text
View/download PDF

7. Parameterized Complexity of -Path Packing

Author

Belmonte, Rémy, Hanaka, Tesshu, Kanzaki, Masaaki, Kiyomi, Masashi, Kobayashi, Yasuaki, Kobayashi, Yusuke, Lampis, Michael, Ono, Hirotaka, Otachi, Yota, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Gąsieniec, Leszek, editor, Klasing, Ralf, editor, and Radzik, Tomasz, editor

Published
2020
Full Text
View/download PDF

8. Four Shorts Stories on Surprising Algorithmic Uses of Treewidth

Author

Marx, Dániel, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Fomin, Fedor V., editor, Kratsch, Stefan, editor, and van Leeuwen, Erik Jan, editor

Published
2020
Full Text
View/download PDF

9. Fixed-Parameter Tractability of Counting Small Minimum (S, T)-Cuts

Author

Bergé, Pierre, Mouscadet, Benjamin, Rimmel, Arpad, Tomasik, Joanna, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Sau, Ignasi, editor, and Thilikos, Dimitrios M., editor

Published
2019
Full Text
View/download PDF

10. Hamiltonicity Below Dirac’s Condition

Author

Jansen, Bart M. P., Kozma, László, Nederlof, Jesper, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Sau, Ignasi, editor, and Thilikos, Dimitrios M., editor

Published
2019
Full Text
View/download PDF

11. Shortest Reconfiguration of Matchings

Author

Bousquet, Nicolas, Hatanaka, Tatsuhiko, Ito, Takehiro, Mühlenthaler, Moritz, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Sau, Ignasi, editor, and Thilikos, Dimitrios M., editor

Published
2019
Full Text
View/download PDF

12. An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number

Author

Kobayashi, Yasuaki, Kobayashi, Yusuke, Miyazaki, Shuichi, Tamaki, Suguru, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Colbourn, Charles J., editor, Grossi, Roberto, editor, and Pisanti, Nadia, editor

Published
2019
Full Text
View/download PDF

13. Parameterized Complexity of Conflict-Free Graph Coloring

Author

Bodlaender, Hans L., Kolay, Sudeshna, Pieterse, Astrid, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Friggstad, Zachary, editor, Sack, Jörg-Rüdiger, editor, and Salavatipour, Mohammad R, editor

Published
2019
Full Text
View/download PDF

14. Modern Aspects of Complexity Within Formal Languages

Author

Fernau, Henning, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Martín-Vide, Carlos, editor, Okhotin, Alexander, editor, and Shapira, Dana, editor

Published
2019
Full Text
View/download PDF

15. Towards Work-Efficient Parallel Parameterized Algorithms

Author

Bannach, Max, Skambath, Malte, Tantau, Till, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Das, Gautam K., editor, Mandal, Partha S., editor, Mukhopadhyaya, Krishnendu, editor, and Nakano, Shin-ichi, editor

Published
2019
Full Text
View/download PDF

16. Complexity Dichotomies for the Minimum -Overlay Problem

Author

Cohen, Nathann, Havet, Frédéric, Mazauric, Dorian, Sau, Ignasi, Watrigant, Rémi, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Brankovic, Ljiljana, editor, Ryan, Joe, editor, and Smyth, William F., editor

Published
2018
Full Text
View/download PDF

17. Reconstructing Generalized Staircase Polygons with Uniform Step Length

Author

Sitchinava, Nodari, Strash, Darren, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Frati, Fabrizio, editor, and Ma, Kwan-Liu, editor

Published
2018
Full Text
View/download PDF

18. On Weak Isomorphism of Rooted Vertex-Colored Graphs

Author

Jaffke, Lars, de Oliveira Oliveira, Mateus, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Brandstädt, Andreas, editor, Köhler, Ekkehard, editor, and Meer, Klaus, editor

Published
2018
Full Text
View/download PDF

19. Safe Sets in Graphs: Graph Classes and Structural Parameters

Author

Águeda, Raquel, Cohen, Nathann, Fujita, Shinya, Legay, Sylvain, Manoussakis, Yannis, Matsui, Yasuko, Montero, Leandro, Naserasr, Reza, Otachi, Yota, Sakuma, Tadashi, Tuza, Zsolt, Xu, Renyu, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Chan, T-H. Hubert, editor, Li, Minming, editor, and Wang, Lusheng, editor

Published
2016
Full Text
View/download PDF

20. On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem

Author

Bonizzoni, Paola, Dondi, Riccardo, Klau, Gunnar W., Pirola, Yuri, Pisanti, Nadia, Zaccaria, Simone, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Cicalese, Ferdinando, editor, Porat, Ely, editor, and Vaccaro, Ugo, editor

Published
2015
Full Text
View/download PDF

21. Parameterized Inapproximability of Degree Anonymization

Author

Bazgan, Cristina, Nichterlein, André, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Cygan, Marek, editor, and Heggernes, Pinar, editor

Published
2014
Full Text
View/download PDF

22. Parameterized Edge Hamiltonicity

Author

Lampis, Michael, Makino, Kazuhisa, Mitsou, Valia, Uno, Yushi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Kratsch, Dieter, editor, and Todinca, Ioan, editor

Published
2014
Full Text
View/download PDF

25. Safe Sets in Graphs: Graph Classes and Structural Parameters

Author

Reza Naserasr, Zsolt Tuza, Yota Otachi, Yasuko Matsui, Yannis Manoussakis, Shinya Fujita, Nathann Cohen, Sylvain Legay, Renyu Xu, Leandro Montero, Tadashi Sakuma, Raquel Águeda, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), University of Castilla-La Mancha (UCLM), Yokohama City University (YCU), Tokai University, Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Japan Advanced Institute of Science and Technology (JAIST), Yamagata University, Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences (MTA), Department of Computer Science - University of Pannonia (DCS), University of Pannonia, Shandong University, T-H. Hubert Chan, Minming Li, and Lusheng Wang

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], interval graph, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, Vertex cover, 0102 computer and information sciences, 02 engineering and technology, Tree-depth, 01 natural sciences, ACM: G.: Mathematics of Computing, Combinatorics, Pathwidth, graph algorithm, Partial k-tree, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Clique-width, treewidth, safe set, Mathematics, Discrete mathematics, 021103 operations research, Interval graph, ACM: F.: Theory of Computation, 1-planar graph, Treewidth, 010201 computation theory & mathematics, fixed-parameter tractability
Abstract

International audience; A safe set of a graph G = (V, E) is a non-empty subset S of V such that for every component A of G[S] and every component B of G[V \ S], we have |A| ≥ |B| whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity of the problem. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between tree-depth and vertex cover number.

Published
2016

26. Co-Clustering Under the Maximum Norm

Author

Vincent Froese, Laurent Bulteau, Rolf Niedermeier, Sepp Hartung, Department of Software Engineering and Theoretical Computer Science (SWT - TUB), Technische Universität Berlin (TU), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Discrete Mathematics (cs.DM), lcsh:T55.4-60.8, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 68Q25, 68R05, 62H30, G.2.1, Context (language use), 0102 computer and information sciences, 02 engineering and technology, bi-clustering, Row and column spaces, 01 natural sciences, lcsh:QA75.5-76.95, Theoretical Computer Science, Combinatorics, Biclustering, Matrix (mathematics), H.3.3, NP-hardness, 0202 electrical engineering, electronic engineering, information engineering, lcsh:Industrial engineering. Management engineering, Partition (number theory), Cluster analysis, Mathematics, Discrete mathematics, Numerical Analysis, SAT solving, F.2.2, I.5.3, True quantified Boolean formula, Block matrix, Ranging, matrix partitioning, fixed-parameter tractability, Computational Mathematics, Computational Theory and Mathematics, 010201 computation theory & mathematics, Norm (mathematics), 020201 artificial intelligence & image processing, lcsh:Electronic computers. Computer science, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], ddc:004, Computer Science - Discrete Mathematics
Abstract

International audience; Co-clustering, that is partitioning a numerical matrix into " homogeneous " submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant of co-clustering where the homogeneity of a submatrix is defined in terms of minimizing the maximum distance between two entries. In this context, we spot several NP-hard, as well as a number of relevant polynomial-time solvable special cases, thus charting the border of tractability for this challenging data clustering problem. For instance, we provide polynomial-time solvability when having to partition the rows and columns into two subsets each (meaning that one obtains four submatrices). When partitioning rows and columns into three subsets each, however, we encounter NP-hardness, even for input matrices containing only values from {0, 1, 2}.

Published
2014

27. Kernelizations for the Hybridization Number Problem on Multiple Nonbinary Trees

Author

Celine Scornavacca, Steven Kelk, Leo van Iersel, Department of Mathematics and Statistics [Christchurch], University of Canterbury [Christchurch], Department of data science and Knowledge Engineering [Maastricht], Maastricht University [Maastricht], Institut des Sciences de l'Evolution de Montpellier (UMR ISEM), École pratique des hautes études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Montpellier (UM)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre National de la Recherche Scientifique (CNRS)-Institut de recherche pour le développement [IRD] : UR226, Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-École Pratique des Hautes Études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Montpellier (UM)-Institut de recherche pour le développement [IRD] : UR226-Centre National de la Recherche Scientifique (CNRS), Evolutionary Intelligence, DKE Scientific staff, and RS: FSE DACS BMI

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Computer Networks and Communications, 0206 medical engineering, Binary number, 0102 computer and information sciences, 02 engineering and technology, phylogenetic network, 01 natural sciences, Theoretical Computer Science, EVENTS, Combinatorics, Computable function, Integer, Quantitative Biology::Populations and Evolution, [INFO]Computer Science [cs], phylogenetic tree, Quantitative Biology - Populations and Evolution, Number problem, Finite set, Mathematics, Discrete mathematics, Kernel (set theory), Phylogenetic tree, Applied Mathematics, ALGORITHMS, PHYLOGENETIC NETWORKS, Populations and Evolution (q-bio.PE), Phylogenetic network, Directed acyclic graph, EVOLUTION, Computational Theory and Mathematics, 010201 computation theory & mathematics, Kernelization, Fixed-parameter tractability, FOS: Biological sciences, kernelization, hybridization number, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], MINIMUM NUMBER, 020602 bioinformatics, Computer Science - Discrete Mathematics
Abstract

A well-studied problem in phylogenetics is to determine the minimum number of hybridization events necessary to explain conflicts among several evolutionary trees, e.g. from different genes. An evolutionary history with hybridization events (or, more generally, reticulations) can be described by a rooted leaf-labelled directed acyclic graph, which is called a phylogenetic network. The reticulation number of such a phylogenetic network can be defined as the sum of all indegrees minus the number of vertices plus one. The considered problem can now formally be stated as follows. Given a finite set \(X\), a collection \(\mathcal {T}\) of rooted phylogenetic trees on \(X\) and \(k\in \mathbb {N}^{+}\), the Hybridization Number problem asks if there exists a rooted phylogenetic network on \(X\) that displays all trees from \(\mathcal {T}\) and has reticulation number at most \(k\). We show that Hybridization Number admits a kernel of size \(4k(5k)^t\) if \(\mathcal {T}\) contains \(t\) (not necessarily binary) rooted phylogenetic trees. In addition, we show a slightly different kernel of size \(20k^2(\varDelta ^+-1)\) with \(\varDelta ^+\) the maximum outdegree of the input trees.

Published
2014

Catalog

Books, media, physical & digital resources
See catalog results