Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Bipartite Graph
Global Constraint
Linear Time
parameterized complexity
Polynomial Time
Subscribe
Academic
Publications
Tractable cases of the extended global cardinality constraint
Tractable cases of the extended global cardinality constraint,10.1007/s106010099079y,Constraints  An International Journal,Marko Samer,Stefan Szei
Edit
Tractable cases of the extended global cardinality constraint
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Marko Samer
,
Stefan Szeider
We study the consistency and domain consistency problem for extended global cardinality (EGC) constraints. An EGC constraint consists of a set X of variables, a set D of values, a domain for each variable x, and a “cardinality set” K(d) of nonnegative integers for each value d. The problem is to instantiate each variable x with a value in D(x) such that for each value d, the number of variables instantiated with d belongs to the cardinality set K(d). It is known that this problem is NPcomplete in general, but solvable in
polynomial time
if all cardinality sets are intervals. First we pinpoint connections between EGC constraints and general factors in graphs. This allows us to extend the known polynomialtime case to certain noninterval cardinality sets. Second we consider EGC constraints under restrictions in terms of the treewidth of the value graph (the
bipartite graph
representing variablevalue pairs) and the cardinalitywidth (the largest integer occurring in the cardinality sets). We show that EGC constraints can be solved in
polynomial time
for instances of bounded treewidth, where the order of the polynomial depends on the treewidth. We show that (subject to the complexity theoretic assumption FPT ≠ W[1]) this dependency cannot be avoided without imposing additional restrictions. If, however, also the cardinalitywidth is bounded, this dependency gets removed and EGC constraints can be solved in linear time.
Journal:
Constraints  An International Journal  CONSTRAINTS
, vol. 16, no. 1, pp. 124, 2011
DOI:
10.1007/s106010099079y
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
(
www.springerlink.com
)
(
www.springerlink.com
)
More »
Citation Context
(1)
...The parameterized complexity of EGC constraints was first studied by Samer and Szeider [
15
] using the treewidth of the value graph as the parameter...
Gregory Gutin
,
et al.
Parameterized Complexity Results for General Factors in Bipartite Grap...
References
(31)
The Tractability of Global Constraints
(
Citations: 16
)
Christian Bessière
,
Emmanuel Hebrard
,
Brahim Hnich
,
Toby Walsh
Conference:
Principles and Practice of Constraint Programming  CP
, pp. 716720, 2004
The Parameterized Complexity of Global Constraints
(
Citations: 9
)
Christian Bessiere
,
Emmanuel Hebrard
,
Brahim Hnich
,
Zeynep Kiziltan
,
Claudeguy Quimper
,
Toby Walsh
Conference:
National Conference on Artificial Intelligence  AAAI
, pp. 235240, 2008
A Tourist Guide through Treewidth
(
Citations: 306
)
Hans L. Bodlaender
Journal:
Acta Cybernetica  ACTAC
, vol. 11, no. 12, pp. 122, 1993
A LinearTime Algorithm for Finding TreeDecompositions of Small Treewidth
(
Citations: 618
)
Hans L. Bodlaender
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 25, no. 6, pp. 13051317, 1996
Discovering Treewidth
(
Citations: 59
)
Hans L. Bodlaender
Conference:
Conference on Current Trends in Theory and Practice of Informatics  SOFSEM
, pp. 116, 2005
Sort by:
Citations
(1)
Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming
Gregory Gutin
,
Eun Jung Kim
,
Arezou Soleimanfallah
,
Stefan Szeider
,
Anders Yeo
Journal:
Algorithmica
, pp. 114, 2011