Zobrazeno 1 - 10
of 30
pro vyhledávání: '"Udi Rotics"'
Publikováno v:
Discrete Applied Mathematics. 205:62-72
We describe the clique-width of path powers by an exact formula, depending only on the number of vertices and the clique number. As a consequence, the clique-width of path powers can be computed in linear time. Path powers are a graph class of unboun
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7b66540e0adac814831d6757cf967aa1
https://doi.org/10.1016/j.dam.2015.11.009
https://doi.org/10.1016/j.dam.2015.11.009
Autor:
Daniel Meister, Udi Rotics
Publikováno v:
Discrete Applied Mathematics. 185:138-167
Bubble models are 2-dimensional representations of proper interval graphs. We consider proper interval graphs that have bubble models of specific properties. We characterise the maximal such proper interval graphs of bounded clique-width and of bound
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c58657c8ec500baaf1edfd133f54664d
https://doi.org/10.1016/j.dam.2014.12.001
https://doi.org/10.1016/j.dam.2014.12.001
Publikováno v:
SIAM Journal on Discrete Mathematics. 23:909-939
Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in monadic second-order logic with second-order quantification on vertex sets, which includes NP-hard proble
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4509e6aaadb42ab76e3e6b8fead45bb4
https://doi.org/10.1137/070687256
https://doi.org/10.1137/070687256
Publikováno v:
Discrete Applied Mathematics. 156(4):462-477
A graph is called equistable when there is a non-negative weight function on its vertices such that a set S of vertices has total weight 1 if and only if S is maximal stable. We show that a necessary condition for a graph to be equistable is sufficie
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::022f19b9722095a7ecaa5bd1b12cb391
Publikováno v:
Discrete Applied Mathematics. 154:1465-1477
An approach for factoring general boolean functions was described in Golumbic and Mintz [Factoring logic functions using graph partitioning, in: Proceedings of IEEE/ACM International Conference on Computer Aided Design, November 1999, pp. 195–198]
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::07d708ac204318a1ce8f587722f7cd1d
https://doi.org/10.1016/j.dam.2005.09.016
https://doi.org/10.1016/j.dam.2005.09.016
Publikováno v:
Electronic Notes in Discrete Mathematics. 22:357-361
In this paper, we present the first polynomial time algorithm for recognizing and factoring read-once functions. The algorithm is based on algorithms for cograph recognition and a new efficient method for checking normality. Its correctness is based
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5806d0b986c77099b489c9fc6dce4640
https://doi.org/10.1016/j.endm.2005.06.076
https://doi.org/10.1016/j.endm.2005.06.076
Autor:
Derek G. Corneil, Udi Rotics
Publikováno v:
SIAM Journal on Computing. 34:825-847
Treewidth is generally regarded as one of the most useful parameterizations of a graph's construction. Clique-width is a similar parameterization that shares one of the powerful properties of treewidth, namely: if a graph is of bounded treewidth (or
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f62430d4a9ff0790962a449e8897d0e2
https://doi.org/10.1137/s0097539701385351
https://doi.org/10.1137/s0097539701385351
Autor:
Daniel Kobler, Udi Rotics
Publikováno v:
Algorithmica. 37:327-346
In a graph G a matching is a set of edges in which no two edges have a common endpoint. An induced matching is a matching in which no two edges are linked by an edge of G. The maximum induced matching (abbreviated MIM) problem is to find the maximum
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::47a87a5a7beec4f0d8e0eb874b5e8ca1
https://doi.org/10.1007/s00453-003-1035-4
https://doi.org/10.1007/s00453-003-1035-4
Autor:
Udi Rotics, Hans L. Bodlaender
Publikováno v:
Algorithmica. 36:375-408
Using the notion of modular decomposition we extend the class of graphs on which both the treewidth and the minimum fill-in can be solved in polynomial time. We show that if C is a class of graphs that are modularly decomposable into graphs that have
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::464eae3445198eb3c855be0dc09a63bd
https://doi.org/10.1007/s00453-003-1026-5
https://doi.org/10.1007/s00453-003-1026-5
Publikováno v:
Discrete Applied Mathematics
Discrete Applied Mathematics, Elsevier, 2015, 187, pp.70-81
Discrete Applied Mathematics, Elsevier, 2015, 187, pp.70-81
International audience; Clique-width of graphs is defined algebraically through operations on graphs with vertex labels. We characterise the clique-width in a combinatorial way by means of partitions of the vertex set, using trees of nested partition
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7f135a140bb4dd77cdcd4185a955add7
https://hal.archives-ouvertes.fr/hal-01022109
https://hal.archives-ouvertes.fr/hal-01022109
