Search

Your search keyword '"Linear-width"' showing total 4 results
Start Over Descriptor "Linear-width"
4 results on '"Linear-width"'

1. Computing Small Search Numbers in Linear Time

Author

Bodlaender, Hans L., Thilikos, Dimitrios M., 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, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Downey, Rod, editor, Fellows, Michael, editor, and Dehne, Frank, editor

Published
2004
Full Text
View/download PDF

2. Outerplanar Obstructions for Matroid Pathwidth.

Author

Koutsonas, Athanassios, Thilikos, Dimitrios M., and Yamazaki, Koichi

Subjects
GRAPH theory, MATROIDS, PATHS & cycles in graph theory, MATHEMATICAL decomposition, EXISTENCE theorems, MATHEMATICAL analysis, COMBINATORICS
Abstract

Abstract: For each k, we provide all outerplanar obstructions for the class of graphs whose cycle matroid has pathwidth at most k. Our proof combines a decomposition lemma for proving lower bounds on matroid pathwidth and a relation between matroid pathwidth and linear-width. Our results imply the existence of a linear algorithm that, given an outerplanar graph, outputs its matroid pathwidth. [Copyright &y& Elsevier]

Published
2011
Full Text
View/download PDF

3. On the monotonicity of games generated by symmetric submodular functions

Author

Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Fomin, Fedor V., Thilikos Touloupas, Dimitrios, Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Fomin, Fedor V., and Thilikos Touloupas, Dimitrios

Abstract

Submodular functions have appeared to be a key tool for proving the monotonicity of several graph searching games. In this paper we provide a general game theoretic framework able to unify old and new monotonicity results in a unique min-max theorem. Our theorem, provides a game theoretic analogue to a wide number of graph theoretic parameters such as linear-width and cutwidth., Postprint (published version)

Published
2001

4. On the monotonicity of games generated by symmetric submodular functions

Author

Fomin, Fedor V., Thilikos Touloupas, Dimitrios, and Universitat Politècnica de Catalunya. Departament de Ciències de la Computació

Subjects
Computer Science::Computer Science and Game Theory, Search games, Informàtica [Àrees temàtiques de la UPC], Cutwidth, Submodularity, Linear-width
Abstract

Submodular functions have appeared to be a key tool for proving the monotonicity of several graph searching games. In this paper we provide a general game theoretic framework able to unify old and new monotonicity results in a unique min-max theorem. Our theorem, provides a game theoretic analogue to a wide number of graph theoretic parameters such as linear-width and cutwidth.

Catalog

Books, media, physical & digital resources
See catalog results