default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDTheoretical Computer Science, Volume 411
Volume 411, Number 1, January 2010
- Dorit S. Hochbaum, Asaf Levin
:
Covering the edges of bipartite graphs using K2, 2 graphs. 1-9 - Laurent Lyaudet:
NP-hard and linear variants of hypergraph partitioning. 10-21 - Kohtaro Tadaki, Tomoyuki Yamakami, Jack C. H. Lin:
Theory of one-tape linear-time Turing machines. 22-43 - Leah Epstein, Rob van Stee:
Maximizing the minimum load for selfish agents. 44-57 - Achour Mostéfaoui, Michel Raynal, Corentin Travers:
Narrowing power vs efficiency in synchronous set agreement: Relationship, algorithms and lower bound. 58-69 - Aldo de Luca, Luca Q. Zamboni:
On graphs of central episturmian words. 70-90 - Gem Stapleton, John Howse, Peter J. Rodgers:
A graph theoretic approach to general Euler diagram drawing. 91-112 - Markus Müller:
Stationary algorithmic probability. 113-130 - Marek Chrobak, Jirí Sgall:
Three results on frequency assignment in linear cellular networks. 131-137 - Martin Anthony, Joel Ratsaby:
Maximal width learning of binary functions. 138-147 - Donatella Merlini, Renzo Sprugnoli:
The relevant prefixes of coloured Motzkin walks: An average case analysis. 148-163 - Hartwig Bosse, Jaroslaw Byrka, Evangelos Markakis:
New algorithms for approximate Nash equilibria in bimatrix games. 164-173 - Xiang-Yang Li, Zheng Sun, Weizhao Wang, Xiaowen Chu, Shaojie Tang, Ping Xu:
Mechanism design for set cover games with selfish element agents. 174-187 - Ulrich Laube, Markus E. Nebel:
Maximum likelihood analysis of algorithms and data structures. 188-212 - Paolo D'Arco, Alfredo De Santis, Anna Lisa Ferrara, Barbara Masucci:
Variations on a theme by Akl and Taylor: Security and tradeoffs. 213-227 - Yun Liu:
Compositions of maximal codes. 228-238 - Allan Borodin, Joan Boyar, Kim S. Larsen, Nazanin Mirmohammadi:
Priority algorithms for graph optimization problems. 239-258 - David Richeson, Paul Winkler, Jim Wiseman:
Itineraries of rigid rotations and diffeomorphisms of the circle. 259-265 - Véronique Terrier:
Simulation of one-way cellular automata by boolean circuits. 266-276 - Mingen Lin, Yang Yang, Jinhui Xu:
On Lazy Bin Covering and Packing problems. 277-284
- Md. Kamrul Hasan, Mohammad Kaykobad, Young-Koo Lee, Sungyoung Lee:
A comprehensive analysis of degree based condition for Hamiltonian cycles. 285-287 - Andrzej Chmielowiec:
Fixed points of the RSA encryption algorithm. 288-292 - Ye Du, Rahul Sami, Yaoyun Shi:
Path auctions with multiple edge ownership. 293-300
Volume 411, Number 2, January 2010
- Ken Kaneiwa, Ken Satoh:
On the complexities of consistency checking for restricted UML class diagrams. 301-323 - Ken-etsu Fujita:
CPS-translation as adjoint. 324-340 - Stephen L. Bloom, Zoltán Ésik:
A Mezei-Wright theorem for categorical algebras. 341-359 - Lan Lin, Stacy J. Prowell, Jesse H. Poore:
An axiom system for sequence-based specification. 360-376 - Ugo Dal Lago, Andrea Masini, Margherita Zorzi:
Quantum implicit computational complexity. 377-409 - Michele Pagani, Lorenzo Tortora de Falco:
Strong normalization property for second order linear logic. 410-444 - Manuel Bodirsky, Hubie Chen:
Peek arc consistency. 445-453 - Laura Bozzelli, Ruggero Lanotte:
Complexity and succinctness issues for linear-time hybrid logics. 454-469 - Patrick Baillot, Damiano Mazza:
Linear logic by levels and bounded time complexity. 470-503 - María Alpuente, Santiago Escobar, Bernhard Gramlich, Salvador Lucas:
On-demand strategy annotations revisited: An improved on-demand evaluation strategy. 504-541 - Alessandro Romanel, Corrado Priami:
On the computational power of BlenX. 542-565 - Robert M. Hierons:
Canonical finite state machines for distributed systems. 566-580
Volume 411, Number 3, January 2010
- Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin:
On stateless multihead automata: Hierarchies and the emptiness problem. 581-593 - Thi Ha Duong Phan, Tran Thi Thu Huong:
On the stability of Sand Piles Model. 594-601 - Bart Kastermans, Steffen Lempp:
Comparing notions of randomness. 602-616 - Elena Czeizler, Lila Kari, Shinnosuke Seki:
On a special class of primitive words. 617-630 - Christian Mathissen:
Definable transductions and weighted logics for texts. 631-659 - Vittorio Bilò, Angelo Fanelli, Michele Flammini, Luca Moscardelli:
When ignorance helps: Graphical multicast cost sharing games. 660-671 - Wanyong Tian, Minming Li, Enhong Chen:
Energy optimal schedules for jobs with multiple active intervals. 672-676
- Colm Ó'Dúnlaing, Natalie Schluter:
A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems. 677-690 - Mario Boley, Tamás Horváth, Axel Poigné, Stefan Wrobel:
Listing closed sets of strongly accessible set systems with applications to data mining. 691-700
Volume 411, Numbers 4-5, January 2010
- Erzsébet Csuhaj-Varjú, Zoltán Ésik:
Preface. 701
- Henrik Björklund, Thomas Schwentick:
On notions of regularity for data languages. 702-715 - Gaëlle Brevier, Romeo Rizzi, Stéphane Vialette:
Complexity issues in color-preserving graph embeddings. 716-729 - Robert Brijder, Miika Langille, Ion Petre:
Extended strings and graphs for simple gene assembly. 730-738 - Jin-yi Cai, Pinyan Lu:
On blockwise symmetric signatures for matchgates. 739-750 - Thomas Colcombet:
Factorization forests for infinite words and applications to countable scattered linear orderings. 751-764 - Jörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, Ariya Isihara, Jan Willem Klop:
Productivity of stream definitions. 765-782 - Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
On the complexity of kings. 783-798 - Michael Hoffmann, Richard M. Thomas:
Notions of hyperbolicity in monoids. 799-811 - Martin Kutrib, Andreas Malcher:
Real-time reversible iterative arrays. 812-822 - Andrea Sattler-Klein:
Some complexity results for prefix Gröbner bases in free monoid rings. 823-833
Volume 411, Number 6, February 2010
- Grzegorz Rozenberg:
Preface. 835-836
- Shlomi Dolev, Hen Fitoussi:
Masking traveling beams: Optical solutions for NP-complete problems, trading space for time. 837-853 - Tobias Friedrich, Nils Hebbinghaus, Frank Neumann:
Plateaus can be harder in multi-objective optimization. 854-864 - Paola Bonizzoni:
Constants and label-equivalence: A decision procedure for reflexive regular splicing languages. 865-877 - Antonio E. Porreca, Giancarlo Mauri, Claudio Zandron:
Non-confluence in divisionless P systems with active membranes. 878-887 - Xingchang Liu, Xiaofan Yang, Shenglin Li, Yong Ding:
Solving the minimum bisection problem using a biologically inspired computational model. 888-896 - Robert Brijder, Hendrik Jan Hoogeboom:
Combining overlap and containment for gene assembly in ciliates. 897-905 - Linqiang Pan, Gheorghe Paun:
Spiking neural P systems: An improved normal form. 906-918 - J. Mark Keil, Jing Liu, Ian McQuillan:
Algorithmic properties of ciliate sequence alignment. 919-925 - Tianshi Chen, Jun He, Guoliang Chen, Xin Yao:
Choosing selection pressure for wide-gap problems. 926-934
Volume 411, Numbers 7-9, February 2010
- Reinhard Pichler, Vadim Savenkov:
Towards practical feasibility of core computation in data exchange. 935-957 - Mauro Mezzini, Marina Moscarini:
Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network. 958-966 - Katerina Asdre, Stavros D. Nikolopoulos:
A polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphs. 967-975 - Matthew de Brecht, Akihiro Yamamoto:
Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data. 976-985 - Tien-Ching Lin, D. T. Lee:
Efficient algorithms for the sum selection problem and k maximum sums problem. 986-994 - Sadish Sadasivam, Huaming Zhang:
NP-Completeness of st-orientations for plane graphs. 995-1003 - Elaine Render, Mark Kambites:
Semigroup automata with rational initial and terminal sets. 1004-1012 - Serafino Cicerone, Gianlorenzo D'Angelo, Gabriele Di Stefano, Daniele Frigioni:
Partially dynamic efficient algorithms for distributed shortest paths. 1013-1037 - Yukun Cheng, Liying Kang, Changhong Lu:
The pos/neg-weighted 1-median problem on tree graphs with subtree-shaped customers. 1038-1044 - Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh:
Iterative compression and exact algorithms. 1045-1053 - Petra Berenbrink, Oliver Schulte:
Evolutionary equilibrium in Bayesian routing games: Specialization and niche formation. 1054-1074 - Pietro di Lena, Luciano Margara:
On the undecidability of the limit behavior of Cellular Automata. 1075-1084 - Chaim Goodman-Strauss:
A hierarchical strongly aperiodic set of tiles in the hyperbolic plane. 1085-1093 - Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang:
Two-group knapsack game. 1094-1103 - Jeff Abrahamson, Ali Shokoufandeh:
Euclidean TSP on two polygons. 1104-1114 - Pawel Gawrychowski, Marin Gutan, Andrzej Kisielewicz:
On the problem of freeness of multiplicative matrix semigroups. 1115-1120 - Carlos Gómez-Rodríguez, Miguel A. Alonso, Manuel Vilares Ferro:
Error-repair parsing schemata. 1121-1139 - Shenpeng Lu, Haodi Feng, Xiuqian Li:
Minimizing the makespan on a single parallel batching machine. 1140-1145 - Nicolas Gast, Bruno Gaujal:
Infinite labeled trees: From rational to Sturmian trees. 1146-1166 - Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, Karol Suchan:
Pursuing a fast robber on a graph. 1167-1181 - Kazuo Iwama, Kazuhisa Seto, Suguru Tamaki:
The complexity of the Hajós calculus for planar graphs. 1182-1191 - Oscar H. Ibarra, Igor Potapov, Hsu-Chun Yen:
On decision problems for parameterized machines. 1192-1201 - Hans L. Bodlaender, Michael R. Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos, Frances A. Rosamond:
Clustering with partial information. 1202-1211 - Mauro Mezzini:
On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs. 1212-1220 - Raphael C. S. Machado, Celina M. H. de Figueiredo, Kristina Vuskovic:
Chromatic index of graphs with no cycle with a unique chord. 1221-1234
Volume 411, Number 10, March 2010
- Moti Yung:
Preface. 1235
- Marius Zimand:
Simple extractors via constructions of cryptographic pseudo-random generators. 1236-1250 - Omer Horvitz, Jonathan Katz:
Bounds on the efficiency of black-box commitment schemes. 1251-1260 - Yannick Chevalier, Michaël Rusinowitch:
Symbolic protocol analysis in the union of disjoint intruder theories: Combining decision procedures. 1261-1282 - Tal Moran, Moni Naor:
Basing cryptographic protocols on tamper-evident seals. 1283-1310
Volume 411, Numbers 11-13, March 2010
- Jifeng He, Tony Hoare:
CSP is a retract of CCS. 1311-1337 - Simona Orzan, Tim A. C. Willemse:
Invariants for Parameterised Boolean Equation Systems. 1338-1371 - Richard W. Barraclough, David W. Binkley, Sebastian Danicic, Mark Harman, Robert M. Hierons, Ákos Kiss, Mike Laurence, Lahcen Ouarbya:
A trajectory-based strict semantics for program slicing. 1372-1386 - Yuxi Fu, Hao Lu:
On the expressiveness of interaction. 1387-1451 - Philippe Gaucher:
Combinatorics of labelling in higher-dimensional automata. 1452-1483 - Sandra Alves, Maribel Fernández, Mário Florido, Ian Mackie:
Gödel's system tau revisited. 1484-1500 - Peter Hines:
Quantum circuit oracles for Abstract Machine computations. 1501-1520 - Manfred Schmidt-Schauß, David Sabel:
On generic context lemmas for higher-order calculi with sharing. 1521-1541
Volume 411, Numbers 14-15, March 2010
- Alexander A. Shvartsman, Pascal Felber:
Editors' preface. 1543
- David Ilcinkas, Dariusz R. Kowalski, Andrzej Pelc:
Fast radio broadcasting with advice. 1544-1557 - Florent Becker, Sergio Rajsbaum, Ivan Rapaport, Eric Rémila:
Average long-lived binary consensus: Quantifying the stabilizing role played by memory. 1558-1566 - Toshimitsu Masuzawa, Sébastien Tixeuil:
Quiescence of self-stabilizing gossiping among mobile agents in graphs. 1567-1582 - Paola Flocchini, David Ilcinkas, Andrzej Pelc, Nicola Santoro:
Remembering without memory: Tree exploration by asynchronous oblivious robots. 1583-1598 - Thomas Sauerwald, Dirk Sudholt:
A self-stabilizing algorithm for cut problems in synchronous networks. 1599-1612 - Pierre Fraigniaud, Emmanuelle Lebhar, Zvi Lotker:
Recovering the long-range links in augmented graphs. 1613-1625 - Davide Bilò, Thomas Erlebach, Matús Mihalák, Peter Widmayer:
Discovery of network properties with all-shortest-paths queries. 1626-1637 - Colin Cooper, Ralf Klasing, Tomasz Radzik:
Locating and repairing faults in a network with mobile agents. 1638-1647 - David Adjiashvili, David Peleg:
Equal-area locus-based convex polygon decomposition. 1648-1667
Volume 411, Numbers 16-18, March 2010
- Well Y. Chou, Chiuyuan Chen:
All-to-all personalized exchange in generalized shuffle-exchange networks. 1669-1684 - Osamu Watanabe, Masaki Yamamoto:
Average-case analysis for the MAX-2SAT problem. 1685-1697 - Henning Fernau:
Parameterized algorithms for d-Hitting Set: The weighted case. 1698-1713 - Katsuhisa Yamanaka, Shin-Ichi Nakano, Yasuko Matsui, Ryuhei Uehara, Kento Nakada:
Efficient enumeration of all ladder lotteries and its application. 1714-1722 - Joxe Gaintzarain, Montserrat Hermo, Paqui Lucio, Marisa Navarro:
Translating propositional extended conjunctions of Horn clauses into Boolean circuits. 1723-1733 - Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, Rodica Mihai:
Comparing First-Fit and Next-Fit for online edge coloring. 1734-1741 - Ching-Lueh Chang, Yuh-Dauh Lyuu:
Optimal bounds on finding fixed points of contraction mappings. 1742-1749 - Viera Borbel'ová, Katarína Cechlárová:
Rotations in the stable b-matching problem. 1750-1762 - Hosam M. Mahmoud:
Distributional analysis of swaps in Quick Select. 1763-1769 - Florentin Ipate:
Bounded sequence testing from deterministic finite state machines. 1770-1784 - Laura Giambruno, Sabrina Mantaci:
Transducers for the bidirectional decoding of prefix codes. 1785-1792 - Viliam Geffert, Jozef Gajdos:
Multiway in-place merging. 1793-1808 - Sujin Shin:
Codes and maximal monoids. 1809-1817 - Arto Salomaa:
Criteria for the matrix equivalence of words. 1818-1827 - Péter Biró, David F. Manlove, Shubham Mittal:
Size versus stability in the marriage problem. 1828-1841 - Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák:
On convex complexity measures. 1842-1854 - Jean Cardinal, Martin Hoefer:
Non-cooperative facility location and covering games. 1855-1876 - Liqi Zhang, Lingfa Lu, Jinjiang Yuan:
Single-machine scheduling under the job rejection constraint. 1877-1882
- Xin Li, Tian Liu:
On exponential time lower bound of Knapsack under backtracking. 1883-1888 - Yoshiaki Nonaka, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita:
The hitting and cover times of Metropolis walks. 1889-1894 - Cheng W. Hong:
The biased, distance-restricted n-in-a-row game for small p. 1895-1897
Volume 411, Number 19, April 2010
- Michael W. Mislove:
Preface. 1899
- Ingo Battenfeld:
Comparing free algebras in Topological and Classical Domain Theory. 1900-1917 - Keye Martin, Ira S. Moskowitz, Gerard Allwein:
Algebraic information theory for binary channels. 1918-1927 - Ivan Lanese, Davide Sangiorgi:
An operational semantics for a calculus for wireless systems. 1928-1948 - Daniele Varacca, Nobuko Yoshida:
Typed event structures and the linear pi-calculus. 1949-1973 - Peng Li, Steve Zdancewic:
Arrows for secure information flow. 1974-1994
Volume 411, Number 20, April 2010
- Grzegorz Rozenberg:
Preface. 1995-1996 - Nicola Cannata, Emanuela Merelli, Irek Ulidowski:
Preface: Hybrid automata and oscillatory behaviour in biological systems. 1997-1998
- Ezio Bartocci, Flavio Corradini, Emanuela Merelli, Luca Tesei:
Detecting synchronisation of biological oscillators by model checking. 1999-2018 - Paolo Ballarini, Maria Luisa Guerriero:
Query-based verification of qualitative trends and oscillations in biochemical systems. 2019-2036 - Dario Campagna, Carla Piazza:
Hybrid automata, reachability, and Systems Biology. 2037-2051 - Luca Bortolussi, Alberto Policriti:
Hybrid dynamics of stochastic programs. 2052-2077
Volume 411, Number 21, May 2010
- Grzegorz Rozenberg:
Preface. 2079-2080 - Eric Bonabeau, David W. Corne, Joshua D. Knowles, Riccardo Poli:
Swarm intelligence theory: A snapshot of the state of the art. 2081-2083
- Dirk Sudholt, Carsten Witt:
Runtime analysis of a binary particle swarm optimizer. 2084-2100 - Ying-Ping Chen, Pei Jiang:
Analysis of particle interaction in particle swarm optimization. 2101-2115 - Peter Vrancx, Katja Verbeeck, Ann Nowé:
Analyzing the dynamics of stigmergetic interactions through pheromone games. 2116-2126 - Arijit Biswas, Swagatam Das, Ajith Abraham, Sambarta Dasgupta:
Stability analysis of the reproduction operator in bacterial foraging optimization. 2127-2139 - Fatih Gökçe, Erol Sahin:
The pros and cons of flocking in the long-range "migration" of mobile robot swarms. 2140-2154
Volume 411, Numbers 22-24, May 2010
- Karell Bertet, Bernard Monjardet:
The multiple facets of the canonical direct unit implicational basis. 2155-2166 - Dongsheng Zhao, Taihe Fan:
Dcpo-completion of posets. 2167-2173
- Nicoletta De Francesco, Giuseppe Lettieri, Luca Martini:
Using abstract interpretation to add type checking for interfaces in Java bytecode verification. 2174-2201 - Simone Tini:
Non-expansive epsilon-bisimulations for probabilistic processes. 2202-2222 - Kohei Honda, Olivier Laurent:
An exact correspondence between a typed pi-calculus and polarised proof-nets. 2223-2238 - Ichiro Hasuo, Yoshinobu Kawabe, Hideki Sakurada:
Probabilistic anonymity via coalgebraic simulations. 2239-2259 - Richard A. Hayden, Jeremy T. Bradley:
A fluid analysis framework for a Markovian process algebra. 2260-2297 - Stéphane Demri, Ranko Lazic, Arnaud Sangnier:
Model checking memoryful linear-time logics over one-counter automata. 2298-2316 - Wim H. Hesselink:
Alternating states for dual nondeterminism in imperative programming. 2317-2330 - Alexander Rabinovich:
Complexity of metric temporal logics with counting and the Pnueli modalities. 2331-2342
Volume 411, Number 25, May 2010
- Grzegorz Rozenberg:
Preface. 2343-2344
- Tseren-Onolt Ishdorj, Alberto Leporati, Linqiang Pan, Xiangxiang Zeng, Xingyi Zhang:
Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources. 2345-2358 - Artiom Alhazov, Chang Li, Ion Petre:
Computing the graph-based parallel complexity of gene assembly. 2359-2367 - Christina Hayes, Tomás Gedeon:
Hyperbolicity of the fixed point set for the simple genetic algorithm. 2368-2383 - Bruno Apolloni, Simone Bassis, Sabrina Gaito, Dario Malchiodi, Italo Zoppis:
Playing monotone games to understand learning behaviors. 2384-2405 - Frank Neumann, Carsten Witt:
Ant Colony Optimization and the minimum spanning tree problem. 2406-2413 - Victor Mitrana, Ion Petre, Vladimir Rogojin:
Accepting splicing systems. 2414-2422
Volume 411, Numbers 26-28, June 2010
- Claire Herrbach, Alain Denise, Serge Dulucq:
Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of a RNA secondary structure alignment algorithm. 2423-2432 - Masafumi Yamashita, Ichiro Suzuki:
Characterizing geometric patterns formable by oblivious anonymous mobile robots. 2433-2453 - O. Shanker:
Complex network dimension and path counts. 2454-2458 - Shlomi Dolev, Elad Michael Schiller, Paul G. Spirakis, Philippas Tsigas:
Game authority for robust and scalable distributed selfish-computer systems. 2459-2466 - Qiang-Sheng Hua, Yuexuan Wang, Dongxiao Yu, Francis C. M. Lau:
Dynamic programming based algorithms for set multicover and multiset multicover problems. 2467-2474 - Guillaume Fertin, Danny Hermelin, Romeo Rizzi, Stéphane Vialette:
Finding common structured patterns in linear graphs. 2475-2486 - Mathilde Bouvel, Elisa Pergola:
Posets and permutations in the duplication-loss model: Minimal permutations with d descents. 2487-2501 - Zeev Nutov:
Approximating minimum power covers of intersecting families and directed edge-connectivity problems. 2502-2512 - Wenbin Chen, Dengpan Yin, Zhengzhang Chen:
Inapproximability results for equations over infinite groups. 2513-2519 - William Hendrix, Matthew C. Schmidt, Paul Breimyer, Nagiza F. Samatova:
Theoretical underpinnings for maximal clique enumeration on perturbed graphs. 2520-2536 - Tongquan Zhang, Ying Yin, Jianping Li:
An improved approximation algorithm for the maximum TSP. 2537-2541 - Spyros Angelopoulos, Allan Borodin:
Randomized priority algorithms. 2542-2558 - Alexander Okhotin, Christian Reitwießner:
Conjunctive grammars with restricted disjunction. 2559-2571 - Joan Boyar, Leah Epstein, Asaf Levin:
Tight results for Next Fit and Worst Fit with resource augmentation. 2572-2580 - Jean Cardinal, Eythan Levy:
Connected vertex covers in dense graphs. 2581-2590 - Shuji Kijima, Masashi Kiyomi, Yoshio Okamoto, Takeaki Uno:
On listing, sampling, and counting the chordal graphs with edge constraints. 2591-2601 - Luis Filipe Coelho Antunes, Andre Souto:
Information measures for infinite sequences. 2602-2611 - Zhiqiang Zhang, Yaoyun Shi:
On the parity complexity measures of Boolean functions. 2612-2618
- Ken-ichi Kawarabayashi, Kenta Ozeki:
A simple algorithm for 4-coloring 3-colorable planar graphs. 2619-2622 - Jun Tarui:
Smallest formulas for the parity of 2k variables are essentially unique. 2623-2627
Volume 411, Numbers 29-30, June 2010
- László Györfi, György Turán, Thomas Zeugmann:
Guest editors' foreword. 2629-2631
- Vladimir Vovk, Alexander Shen:
Prequential randomness and probability. 2632-2646 - Alexey V. Chernov, Yuri Kalnishkan, Fedor Zhdanov, Vladimir Vovk:
Supermartingales in prediction with expert advice. 2647-2669 - Indraneel Mukherjee, Robert E. Schapire:
Learning with continuous experts using drifting games. 2670-2683 - Ronald Ortner:
Online regret bounds for Markov decision processes with deterministic transitions. 2684-2695 - Ohad Shamir, Sivan Sabato, Naftali Tishby:
Learning and generalization with the information bottleneck. 2696-2711 - András Antos, Varun Grover, Csaba Szepesvári:
Active learning in heteroscedastic noise. 2712-2728 - Dana Angluin, James Aspnes, Lev Reyzin:
Optimally learning social networks with activations and suppressions. 2729-2740 - Leonor Becerra-Bonache, John Case, Sanjay Jain, Frank Stephan:
Iterative learning of simple external contextual languages. 2741-2756 - Sanjay Jain, Steffen Lange, Samuel E. Moelius, Sandra Zilles:
Incremental learning with temporary memory. 2757-2772
Volume 411, Numbers 31-33, June 2010
- Tomoko Izumi, Taisuke Izumi, Hirotaka Ono, Koichi Wada:
Approximability and inapproximability of the minimum certificate dispersal problem. 2773-2783 - Tamás Horváth, Jan Ramon:
Efficient frequent connected subgraph mining in graphs of bounded tree-width. 2784-2797 - Pavlos S. Efraimidis, Lazaros Tsavlidis, George B. Mertzios:
Window-games between TCP flows. 2798-2817 - Jiao-Fen Li, Xi-Yan Hu, Lei Zhang:
Dykstra's algorithm for constrained least-squares doubly symmetric matrix problems. 2818-2826 - Wai-Fong Chuan, Hui-Ling Ho:
Factors of characteristic words: Location and decompositions. 2827-2846 - Amitai Armon, Adi Avidor, Oded Schwartz:
Cooperative TSP. 2847-2863 - Hans Kleine Büning, Anja Remshagen:
An upper bound for the circuit complexity of existentially quantified Boolean formulas. 2864-2870 - Deshi Ye, Xin Han, Guochuan Zhang:
Deterministic on-line call control in cellular networks. 2871-2877 - Yen-Chiu Chen, Hsin-Wen Wei, Pei-Chi Huang, Wei-Kuan Shih, Tsan-sheng Hsu:
The bridge-connectivity augmentation problem with a partition constraint. 2878-2889 - Qian Cao, Zhaohui Liu:
Online scheduling with reassignment on two uniform machines. 2890-2898 - Leah Epstein:
Two-dimensional online bin packing with rotation. 2899-2911 - Pao-Lien Lai, Hong-Chun Hsu, Chang-Hsiung Tsai, Iain A. Stewart:
A class of hierarchical graphs as topologies for interconnection networks. 2912-2924 - Travis Gagie, Giovanni Manzini:
Move-to-Front, Distance Coding, and Inversion Frequencies revisited. 2925-2944 - Samuel Alexandre Vidal:
An optimal algorithm to generate rooted trivalent diagrams and rooted triangular maps. 2945-2967 - Andreas Brandstädt, Van Bang Le, Dieter Rautenbach:
Exact leaf powers. 2968-2977 - Q. Q. Nong, T. C. Edwin Cheng, C. T. Ng:
A polynomial-time algorithm for the weighted link ring loading problem with integer demand splitting. 2978-2986 - Wouter Gelade:
Succinctness of regular expressions with interleaving, intersection and counting. 2987-2998
- Petr Kurka:
Erratum to: Entropy of Turing machines with moving head. 2999-3000
Volume 411, Numbers 34-36, July 2010
- Costas Busch, Marios Mavronicolas:
An efficient counting network. 3001-3030 - Tal Mizrahi, Yoram Moses:
Continuous consensus with ambiguous failures. 3031-3041 - Raphael Yuster:
Single source shortest paths in H-minor free graphs. 3042-3047 - Guy Feigenblat, Ofra Itzhaki, Ely Porat:
The frequent items problem, under polynomial decay, in the streaming model. 3048-3054 - Nicolas Bourgeois, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos:
Approximating the max-edge-coloring problem. 3055-3067 - Romain Ravaux:
Decomposing trees with large diameter. 3068-3072 - Leah Epstein, Csanád Imreh, Asaf Levin:
Class constrained bin packing revisited. 3073-3089 - Frank Drewes, Berthold Hoffmann, Dirk Janssens, Mark Minas:
Adaptive star grammars and their languages. 3090-3109 - Richard Groult, Gwénaël Richomme:
Optimality of some algorithms to detect quasiperiodicities. 3110-3122 - Adam Bains, Therese Biedl:
Reconstructing hv-convex multi-coloured polyominoes. 3123-3128 - Leah Epstein, Asaf Levin:
Improved randomized results for the interval selection problem. 3129-3135 - Péter Biró, Tamás Fleiner, Robert W. Irving, David F. Manlove:
The College Admissions problem with lower and common quotas. 3136-3153 - Zohir Bouzid, Maria Gradinariu Potop-Butucaru, Sébastien Tixeuil:
Optimal Byzantine-resilient convergence in uni-dimensional robot networks. 3154-3168 - Éric Duchêne, Michel Rigo:
Invariant games. 3169-3180 - Luke Mathieson:
The parameterized complexity of editing graphs for bounded degeneracy. 3181-3187 - Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin:
CSP duality and trees of bounded pathwidth. 3188-3208 - Arseny M. Shur:
Growth rates of complexity of power-free languages. 3209-3223 - Alessandro Cincotti:
N-player partizan games. 3224-3234 - Ralf Klasing, Adrian Kosowski, Alfredo Navarra:
Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring. 3235-3246 - Shan Zhou, Hao Li, Guanghui Wang:
Algorithm for two disjoint long paths in 2-connected graphs. 3247-3254 - Markus Kuba, Alois Panholzer:
A combinatorial approach to the analysis of bucket recursive trees. 3255-3273 - Dominik D. Freydenberger, Daniel Reidenbach:
Existence and nonexistence of descriptive patterns. 3274-3286
- Zhendong Shao, Roberto Solis-Oba:
L(2, 1)-Labelings on the composition of n graphs. 3287-3292 - Paolo Ferragina, Igor Nitto, Rossano Venturini:
On compact representations of All-Pairs-Shortest-Path-Distance matrices. 3293-3300
Volume 411, Number 37, August 2010
- Frédéric Blanqui, Claude Kirchner, Colin Riba:
On the confluence of lambda-calculus with conditional rewriting. 3301-3327 - Luca Padovani:
Contract-based discovery of Web services modulo simple orchestrators. 3328-3347 - María Alpuente, Marco Comini, Santiago Escobar, Moreno Falaschi, José Iborra:
A compact fixpoint semantics for term rewriting systems. 3348-3371 - Robert M. Hierons:
Checking experiments for stream X-machines. 3372-3385 - Russell O'Connor, Bas Spitters:
A computer-verified monadic functional implementation of the integral. 3386-3402
Volume 411, Numbers 38-39, August 2010
- Sebastian Maneth:
Preface. 3403
- Markus Holzer, Andreas Maletti:
An nlogn algorithm for hyper-minimizing a (minimized) deterministic automaton. 3404-3413 - Giusi Castiglione, Antonio Restivo, Marinella Sciortino:
On extremal cases of Hopcroft's algorithm. 3414-3422 - Pascal Caron, Jean-Marc Champarnaud, Ludovic Mignot:
Acyclic automata and small expressions using multi-tilde-bar operators. 3423-3435 - Rusins Freivalds:
Amount of nonconstructivity in deterministic finite automata. 3436-3443 - Pierre Ganty, Nicolas Maquet, Jean-François Raskin:
Fixed point guided abstraction refinement for alternating automata. 3444-3459 - Tayssir Touili, Mohamed Faouzi Atig:
Verifying parallel programs with dynamic communication structures. 3460-3468 - Pierre-Cyrille Héam, Cyril Nicaud, Sylvain Schmitz:
Parametric random generation of deterministic tree automata. 3469-3480 - Kazuhiro Inaba, Haruo Hosoya:
Compact representation for answer sets of n-ary regular queries. 3481-3492 - Akio Fujiyoshi:
Recognition of directed acyclic graphs by spanning tree automata. 3493-3506 - Adam Clarridge, Kai Salomaa:
Analysis of a cellular automaton model for car traffic with a slow-to-stop rule. 3507-3515 - Martin Kutrib, Andreas Malcher:
Cellular automata with sparse communication. 3516-3526
Volume 411, Numbers 40-42, September 2010
- Alain Denise, Yann Ponty, Michel Termier:
Controlled non-uniform random generation of decomposable structures. 3527-3552 - Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Hadas Shachnai, Mordechai Shalom, Tami Tamir, Shmuel Zaks:
Minimizing total busy time in parallel scheduling with application to optical networks. 3553-3562 - Paolo Ciancarini, Gian Piero Favini:
Playing the perfect Kriegspiel endgame. 3563-3577 - C. T. Ng, Shisheng Li, T. C. Edwin Cheng, Jinjiang Yuan:
Preemptive scheduling with simple linear deterioration on a single machine. 3578-3586 - Xin Han, Tak Wah Lam, Lap-Kei Lee, Isaac Kar-Keung To, Prudence W. H. Wong:
Deadline scheduling and power management for speed bounded processors. 3587-3600 - Pim van 't Hof, Daniël Paulusma, Johan M. M. van Rooij:
Computing role assignments of chordal graphs. 3601-3613 - Gang Yu, Xiaoxiao Ma, Yong Shen, Wenbao Han:
Provable secure identity based generalized signcryption scheme. 3614-3624 - Paul C. Bell, Jean-Charles Delvenne, Raphaël M. Jungers, Vincent D. Blondel:
The continuous Skolem-Pisot problem. 3625-3634 - Yasuko Matsui, Ryuhei Uehara, Takeaki Uno:
Enumeration of the perfect sequences of a chordal graph. 3635-3641 - Shisheng Li, Jinjiang Yuan:
Parallel-machine scheduling with deteriorating jobs and rejection. 3642-3650 - Weifan Wang, Stephen Finbow, Ping Wang:
The surviving rate of an infected network. 3651-3660 - Filip Goldefus, Tomás Masopust, Alexander Meduna:
Left-forbidding cooperating distributed grammar systems. 3661-3667 - Michelangelo Bucci, Aldo de Luca, Alessandro De Luca:
On the number of episturmian palindromes. 3668-3684 - Daniel Meister:
Treewidth and minimum fill-in on permutation graphs in linear time. 3685-3700 - Marek Cygan, Marcin Pilipczuk:
Exact and approximate bandwidth. 3701-3713 - Charilaos Efthymiou, Paul G. Spirakis:
Sharp thresholds for Hamiltonicity in random intersection graphs. 3714-3730 - Yun Bao Huang, William D. Weakley:
A note on the complexity of C∞-words. 3731-3735 - Jianer Chen, Iyad A. Kanj, Ge Xia:
Improved upper bounds for vertex cover. 3736-3756 - András Csernenszky:
The Picker-Chooser diameter game. 3757-3762 - Pao-Lien Lai, Chang-Hsiung Tsai:
Embedding of tori and grids into twisted cubes. 3763-3773 - Tomás Dvorák, Václav Koubek:
Computational complexity of long paths and cycles in faulty hypercubes. 3774-3786
- Michael Okun:
Strong order-preserving renaming in the synchronous message passing model. 3787-3794 - Hagai Cohen, Ely Porat:
Fast set intersection and two-patterns matching. 3795-3800
Volume 411, Number 43, October 2010
- Vlady Ravelomanana:
Birth and growth of multicyclic components in random hypergraphs. 3801-3813 - Yair Dombb, Ohad Lipsky, Benny Porat, Ely Porat, Asaf Tsur:
The approximate swap and mismatch edit distance. 3814-3822 - Costas Busch, Srikanta Tirthapura:
Concurrent counting is harder than queuing. 3823-3833 - Anthony Bonato, Ehsan Chiniforooshan, Pawel Pralat:
Cops and Robbers from a distance. 3834-3844 - Allan Scott, Ulrike Stege:
Parameterized pursuit-evasion games. 3845-3858 - Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara:
Reconstruction of interval graphs. 3859-3866
- Tomi A. Pasanen:
Random binary search tree with equal elements. 3867-3872 - Junlei Zhu, Yuehua Bu:
Equitable and equitable list colorings of graphs. 3873-3876 - Gianluca Caterina, Bruce M. Boghosian:
An order-preserving property of additive invariants for Takesue-type reversible cellular automata. 3877-3881
Volume 411, Numbers 44-46, October 2010
- Zhi-Han Gao, Fang-Wei Fu:
The minimal polynomial of a sequence obtained from the componentwise linear transformation of a linear recurring sequence. 3883-3893 - María Isabel Herrero, Gabriela Jeronimo, Juan Sabia:
Computing isolated roots of sparse polynomial systems in affine space. 3894-3904 - Pierluigi Frisco, Oscar H. Ibarra:
On sets of numbers accepted by P/T systems composed by join. 3905-3916 - Wilfried Huss, Ecaterina Sava, Wolfgang Woess:
Entropy sensitivity of languages defined by infinite automata, via Markov chains with forbidden transitions. 3917-3922 - Chan-Shuo Wu, Guan-Shieng Huang:
A metric for rooted trees with unlabeled vertices based on nested parentheses. 3923-3931 - Arturo Carpi, Valerio D'Alonzo:
On factors of synchronized sequences. 3932-3937 - Kei Uchizawa, Takao Nishizeki, Eiji Takimoto:
Energy and depth of threshold circuits. 3938-3946 - Yumei Huo, Joseph Y.-T. Leung:
Fast approximation algorithms for job scheduling with processing set restrictions. 3947-3955 - Xin Han, Kazuhisa Makino:
Online removable knapsack with limited cuts. 3956-3964 - Linda Morales, Ivan Hal Sudborough:
A quadratic lower bound for Topswops. 3965-3970 - Dariusz Dereniowski:
Phutball is PSPACE-hard. 3971-3978 - Shunsuke Ota, Ehab Morsy, Hiroshi Nagamochi:
A plane graph representation of triconnected graphs. 3979-3993 - Camil Demetrescu, Bruno Escoffier, Gabriel Moruz, Andrea Ribichini:
Adapting parallel algorithms to the W-Stream model, with applications to graph problems. 3994-4004
- Jianxin Wang, Wenjun Li, Jianer Chen:
A parameterized algorithm for the hyperplane-cover problem. 4005-4009 - Emmanuel Jeandel:
The periodic domino problem revisited. 4010-4016 - Eyal Ackerman, Oren Ben-Zwi, Guy Wolfovitz:
Combinatorial model and bounds for target set selection. 4017-4022 - Vadim V. Lozin:
A decidability result for the dominating set problem. 4023-4027
Volume 411, Number 47, October 2010
- Olga Grinchtein, Bengt Jonsson, Martin Leucker:
Learning of event-recording automata. 4029-4054 - María Alpuente, Demis Ballis, Francisco J. Correa, Moreno Falaschi:
An integrated framework for the diagnosis and correction of rule-based programs. 4055-4101 - Lars Birkedal, Kristian Støvring, Jacob Thamsborg:
The category-theoretic solution of recursive metric-space equations. 4102-4122 - Ron van der Meyden, Chenyi Zhang:
A comparison of semantic models for noninterference. 4123-4147
Volume 411, Number 48, November 2010
- Paola Bonizzoni, Clelia de Felice, Rosalba Zizza:
A characterization of (regular) circular languages generated by monotone complete splicing systems. 4149-4161 - Florin Manea:
A series of algorithmic results related to the iterated hairpin completion. 4162-4178 - Neal G. Anderson:
On the physical implementation of logical transformations: Generalized L-machines. 4179-4199 - Kok Kiong Tan, Jiancheng Lv, Zhang Yi, Sunan Huang:
Adaptive multiple minor directions extraction in parallel using a PCA neural network. 4200-4215
Volume 411, Number 49, November 2010
- Andreas Darmann, Ulrich Pferschy, Joachim Schauer:
Resource allocation with time intervals. 4217-4234 - Jia-Jie Liu:
Distinct squares in run-length encoded strings. 4235-4241 - Huaming Zhang, Xin He:
A generalized greedy routing algorithm for 2-connected graphs. 4242-4252 - Minghui Jiang:
On the parameterized complexity of some optimization problems related to multiple-interval graphs. 4253-4262 - Brandon Blakeley, Francine Blanchet-Sadri, Josh Gunter, Narad Rampersad:
On the complexity of deciding avoidability of sets of partial words. 4263-4271
Volume 411, Number 50, November 2010
- Giovanna D'Agostino, Giacomo Lenzi:
On the µ-calculus over transitive and finite transitive frames. 4273-4290 - Ruggero Lanotte, Andrea Maggiolo-Schettini, Angelo Troina:
Weak bisimulation for Probabilistic Timed Automata. 4291-4322 - Vladimir V. Rybakov:
Rules admissible in transitive temporal logic TS4, sufficient condition. 4323-4332 - Filip Maric:
Formal verification of a modern SAT solver by shallow embedding into Isabelle/HOL. 4333-4356
Volume 411, Numbers 51-52, December 2010
- John Tang Boyland, Giuseppe Castagna:
Preface. 4357
- Eijiro Sumii:
A bisimulation-like proof method for contextual properties in untyped lambda-calculus with references and deallocation. 4358-4378 - Ivana Filipovic, Peter W. O'Hearn, Noam Rinetzky, Hongseok Yang:
Abstraction for concurrent objects. 4379-4398 - Luís Caires, Hugo Torres Vieira:
Conversation types. 4399-4440 - Mauro Jaskelioff, Eugenio Moggi:
Monad transformers as monoid transformers. 4441-4466
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-10-22 02:16 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
