Search

Your search keyword '"Niedermeier, Rolf"' showing total 1,271 results
Start Over Author "Niedermeier, Rolf"
1,271 results on '"Niedermeier, Rolf"'

151. Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks

Author

Bentert, Matthias, van Bevern, René, Nichterlein, André, Niedermeier, Rolf, 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, Fernández Anta, Antonio, editor, Jurdzinski, Tomasz, editor, Mosteiro, Miguel A., editor, and Zhang, Yanyong, editor

Published
2017
Full Text
View/download PDF

153. Assessing the Computational Complexity of Multi-layer Subgraph Detection

Author

Bredereck, Robert, Komusiewicz, Christian, Kratsch, Stefan, Molter, Hendrik, Niedermeier, Rolf, Sorge, Manuel, 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, Fotakis, Dimitris, editor, Pagourtzis, Aris, editor, and Paschos, Vangelis Th., editor

Published
2017
Full Text
View/download PDF

159. Polynomial Time Data Reduction for Dominating Set

Author

Alber, Jochen, Fellows, Michael R., and Niedermeier, Rolf

Subjects
Computer Science - Data Structures and Algorithms, F.2.2, G.2.1, G.2.2
Abstract

Dealing with the NP-complete Dominating Set problem on undirected graphs, we demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that Dominating Set restricted to planar graphs has a so-called problem kernel of linear size, achieved by two simple and easy to implement reduction rules. Moreover, having implemented our reduction rules, first experiments indicate the impressive practical potential of these rules. Thus, this work seems to open up a new and prospective way how to cope with one of the most important problems in graph theory and combinatorial optimization., Comment: 25 pages, 4 figures (using 8 files), extended abstract entitled "Efficient Data Reduction for Dominating Set: A Linear Problem Kernel for the Planar Case" appeared in the Proceedings of the 8th SWAT 2002, LNCS 2368, pages 150-159, Springer-Verlag, 2002

Published
2002

160. Parameterized Intractability of Motif Search Problems

Author

Fellows, Michael R., Gramm, Jens, and Niedermeier, Rolf

Subjects
Computer Science - Computational Complexity, F.2, F.2.2, J.3
Abstract

We show that Closest Substring, one of the most important problems in the field of biological sequence analysis, is W[1]-hard when parameterized by the number k of input strings (and remains so, even over a binary alphabet). This problem is therefore unlikely to be solvable in time O(f(k)\cdot n^{c}) for any function f of k and constant c independent of k. The problem can therefore be expected to be intractable, in any practical sense, for k>=3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, although both problems are NP-complete. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our W[1]-hardness result for Closest Substring generalizes to Consensus Patterns, a problem of similar significance in computational biology., Comment: 21 pages, 5 figures; an extended abstract of this paper was presented at the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), Springer-Verlag, LNCS 2285, pages 262--273, held in Juan-Les-Pins, France, March~14--16, 2002

Published
2002

165. Twins in Subdivision Drawings of Hypergraphs

Author

van Bevern, René, Kanj, Iyad, Komusiewicz, Christian, Niedermeier, Rolf, Sorge, Manuel, 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, Hu, Yifan, editor, and Nöllenburg, Martin, editor

Published
2016
Full Text
View/download PDF

171. A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths

Author

Bazgan, Cristina, Nichterlein, André, Niedermeier, Rolf, 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, Paschos, Vangelis Th., editor, and Widmayer, Peter, editor

Published
2015
Full Text
View/download PDF

172. The Complexity of Finding Effectors

Author

Bulteau, Laurent, Fafianie, Stefan, Froese, Vincent, Niedermeier, Rolf, Talmon, Nimrod, 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, Jain, Rahul, editor, Jain, Sanjay, editor, and Stephan, Frank, editor

Published
2015
Full Text
View/download PDF

173. Modification-Fair Cluster Editing

Author

Froese, Vincent, Kellerhals, Leon, and Niedermeier, Rolf

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), General Medicine, MathematicsofComputing_DISCRETEMATHEMATICS, Machine Learning (cs.LG)
Abstract

The classic Cluster Editing problem (also known as Correlation Clustering) asks to transform a given graph into a disjoint union of cliques (clusters) by a small number of edge modifications. When applied to vertex-colored graphs (the colors representing subgroups), standard algorithms for the NP-hard Cluster Editing problem may yield solutions that are biased towards subgroups of data (e.g., demographic groups), measured in the number of modifications incident to the members of the subgroups. We propose a modification fairness constraint which ensures that the number of edits incident to each subgroup is proportional to its size. To start with, we study Modification-Fair Cluster Editing for graphs with two vertex colors. We show that the problem is NP-hard even if one may only insert edges within a subgroup; note that in the classic "non-fair" setting, this case is trivially polynomial-time solvable. However, in the more general editing form, the modification-fair variant remains fixed-parameter tractable with respect to the number of edge edits. We complement these and further theoretical results with an empirical analysis of our model on real-world social networks where we find that the price of modification-fairness is surprisingly low, that is, the cost of optimal modification-fair differs from the cost of optimal "non-fair" solutions only by a small percentage., Comment: Accepted at AAAI 2022

Published
2022

176. Combining Clickstream Analyses and Graph-Modeled Data Clustering for Identifying Common Response Processes

Author

Ulitzsch, Esther, He, Qiwei, Ulitzsch, Vincent, Molter, Hendrik, Nichterlein, André, Niedermeier, Rolf, Pohl, Steffi, Ulitzsch, Esther, He, Qiwei, Ulitzsch, Vincent, Molter, Hendrik, Nichterlein, André, Niedermeier, Rolf, and Pohl, Steffi

Abstract

Complex interactive test items are becoming more widely used in assessments. Being computer-administered, assessments using interactive items allow logging time-stamped action sequences. These sequences pose a rich source of information that may facilitate investigating how examinees approach an item and arrive at their given response. There is a rich body of research leveraging action sequence data for investigating examinees’ behavior. However, the associated timing data have been considered mainly on the item-level, if at all. Considering timing data on the action-level in addition to action sequences, however, has vast potential to support a more fine-grained assessment of examinees’ behavior. We provide an approach that jointly considers action sequences and action-level times for identifying common response processes. In doing so, we integrate tools from clickstream analyses and graph-modeled data clustering with psychometrics. In our approach, we (a) provide similarity measures that are based on both actions and the associated action-level timing data and (b) subsequently employ cluster edge deletion for identifying homogeneous, interpretable, well-separated groups of action patterns, each describing a common response process. Guidelines on how to apply the approach are provided. The approach and its utility are illustrated on a complex problem-solving item from PIAAC 2012.

Published
2023

177. Network-Based Dissolution

Author

van Bevern, René, Bredereck, Robert, Chen, Jiehua, Froese, Vincent, Niedermeier, Rolf, Woeginger, Gerhard J., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Csuhaj-Varjú, Erzsébet, editor, Dietzfelbinger, Martin, editor, and Ésik, Zoltán, editor

Published
2014
Full Text
View/download PDF

178. Combinatorial Voter Control in Elections

Author

Chen, Jiehua, Faliszewski, Piotr, Niedermeier, Rolf, Talmon, Nimrod, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Csuhaj-Varjú, Erzsébet, editor, Dietzfelbinger, Martin, editor, and Ésik, Zoltán, editor

Published
2014
Full Text
View/download PDF

179. Star Partitions of Perfect Graphs

Author

van Bevern, René, Bredereck, Robert, Bulteau, Laurent, Chen, Jiehua, Froese, Vincent, Niedermeier, Rolf, Woeginger, Gerhard J., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Esparza, Javier, editor, Fraigniaud, Pierre, editor, Husfeldt, Thore, editor, and Koutsoupias, Elias, editor

Published
2014
Full Text
View/download PDF

180. Co-Clustering Under the Maximum Norm

Author

Bulteau, Laurent, Froese, Vincent, Hartung, Sepp, Niedermeier, Rolf, 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, Ahn, Hee-Kap, editor, and Shin, Chan-Su, editor

Published
2014
Full Text
View/download PDF

181. The Parameterized Complexity of the Rainbow Subgraph Problem

Author

Hüffner, Falk, Komusiewicz, Christian, Niedermeier, Rolf, Rötzschke, Martin, 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

182. The Complexity of Degree Anonymization by Vertex Addition

Author

Bredereck, Robert, Froese, Vincent, Hartung, Sepp, Nichterlein, André, Niedermeier, Rolf, Talmon, Nimrod, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Gu, Qianping, editor, Hell, Pavol, editor, and Yang, Boting, editor

Published
2014
Full Text
View/download PDF

193. Effective and Efficient Data Reduction for the Subset Interconnection Design Problem

Author

Chen, Jiehua, Komusiewicz, Christian, Niedermeier, Rolf, Sorge, Manuel, Suchý, Ondřej, Weller, Mathias, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Cai, Leizhen, editor, Cheng, Siu-Wing, editor, and Lam, Tak-Wah, editor

Published
2013
Full Text
View/download PDF

194. How to Put through Your Agenda in Collective Binary Decisions

Author

Alon, Noga, Bredereck, Robert, Chen, Jiehua, Kratsch, Stefan, Niedermeier, Rolf, Woeginger, Gerhard J., 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, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Perny, Patrice, editor, Pirlot, Marc, editor, and Tsoukiàs, Alexis, editor

Published
2013
Full Text
View/download PDF

195. A Parameterized Complexity Analysis of Combinatorial Feature Selection Problems

Author

Froese, Vincent, van Bevern, René, Niedermeier, Rolf, Sorge, Manuel, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Chatterjee, Krishnendu, editor, and Sgall, Jirí, editor

Published
2013
Full Text
View/download PDF

196. On Explaining Integer Vectors by Few Homogenous Segments

Author

Bredereck, Robert, Chen, Jiehua, Hartung, Sepp, Komusiewicz, Christian, Niedermeier, Rolf, Suchý, Ondřej, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dehne, Frank, editor, Solis-Oba, Roberto, editor, and Sack, Jörg-Rüdiger, editor

Published
2013
Full Text
View/download PDF

197. A Refined Complexity Analysis of Degree Anonymization in Graphs

Author

Hartung, Sepp, Nichterlein, André, Niedermeier, Rolf, Suchý, Ondřej, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fomin, Fedor V., editor, Freivalds, Rūsiņš, editor, Kwiatkowska, Marta, editor, and Peleg, David, editor

Published
2013
Full Text
View/download PDF

198. Pattern-Guided k-Anonymity

Author

Bredereck, Robert, Nichterlein, André, Niedermeier, Rolf, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fellows, Michael, editor, Tan, Xuehou, editor, and Zhu, Binhai, editor

Published
2013
Full Text
View/download PDF

199. Evaluation of ILP-Based Approaches for Partitioning into Colorful Components

Author

Bruckner, Sharon, Hüffner, Falk, Komusiewicz, Christian, Niedermeier, Rolf, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bonifaci, Vincenzo, editor, Demetrescu, Camil, editor, and Marchetti-Spaccamela, Alberto, editor

Published
2013
Full Text
View/download PDF

200. Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage

Author

Hüffner, Falk, Komusiewicz, Christian, Liebtrau, Adrian, Niedermeier, Rolf, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Istrail, Sorin, editor, Pevzner, Pavel, editor, Waterman, Michael S., editor, Cai, Zhipeng, editor, Eulenstein, Oliver, editor, Janies, Daniel, editor, and Schwartz, Daniel, editor

Published
2013
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results