On the Complexity of the G-Reconstruction Problem (English)
- New search for: Dvořák, Zdeněk
- New search for: Jelínek, Vít
- New search for: Dvořák, Zdeněk
- New search for: Jelínek, Vít
In:
Algorithms and Computation
1
;
196-205
;
2005
- Article/Chapter (Book) / Electronic Resource
-
Title:On the Complexity of the G-Reconstruction Problem
-
Contributors:Dvořák, Zdeněk ( author ) / Jelínek, Vít ( author )
-
Published in:Algorithms and Computation , 1 ; 196-205Lecture Notes in Computer Science ; 3827, 1 ; 196-205
-
Publisher:
- New search for: Springer Berlin Heidelberg
-
Place of publication:Berlin, Heidelberg
-
Publication date:2005-01-01
-
Size:10 pages
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Article/Chapter (Book)
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Source:
Table of contents eBook
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
Algorithmic Problems in Wireless Ad Hoc NetworksYao, Frances F. et al. | 2005
- 2
-
Probability and RecursionEtessami, Kousha / Yannakakis, Mihalis et al. | 2005
- 5
-
Embedding Point Sets into Plane Graphs of Small DilationEbbers-Baumann, Annette / Grüne, Ansgar / Karpinski, Marek / Klein, Rolf / Knauer, Christian / Lingas, Andrzej et al. | 2005
- 17
-
The Layered Net Surface Problems in Discrete Geometry and Medical Image SegmentationWu, Xiaodong / Chen, Danny Z. / Li, Kang / Sonka, Milan et al. | 2005
- 28
-
Separability with OutliersHar-Peled, Sariel / Koltun, Vladlen et al. | 2005
- 40
-
Casting an Object with a CoreAhn, Hee-Kap / Bae, Sang Won / Cheng, Siu-Wing / Chwa, Kyung-Yong et al. | 2005
- 50
-
Sparse Geometric Graphs with Small DilationAronov, Boris / Berg, Mark / Cheong, Otfried / Gudmundsson, Joachim / Haverkort, Herman / Vigneron, Antoine et al. | 2005
- 60
-
Multiple Polyline to Polygon MatchingTănase, Mirela / Veltkamp, Remco C. / Haverkort, Herman et al. | 2005
- 71
-
Minimizing a Monotone Concave Function with Laminar Covering ConstraintsSakashita, Mariko / Makino, Kazuhisa / Fujishige, Satoru et al. | 2005
- 82
-
Almost Optimal Solutions for Bin Coloring ProblemsLin, Mingen / Lin, Zhiyong / Xu, Jinhui et al. | 2005
- 92
-
GEN-LARAC: A Generalized Approach to the Constrained Shortest Path Problem Under Multiple Additive ConstraintsXiao, Ying / Thulasiraman, Krishnaiyan / Xue, Guoliang et al. | 2005
- 106
-
Simultaneous MatchingsElbassioni, Khaled / Katriel, Irit / Kutz, Martin / Mahajan, Meena et al. | 2005
- 116
-
An Optimization Problem Related to VoD BroadcastingKameda, Tsunehiko / Sun, Yi / Goddyn, Luis et al. | 2005
- 126
-
A Min-Max Relation on Packing Feedback Vertex SetsChen, Xujin / Ding, Guoli / Hu, Xiaodong / Zang, Wenan et al. | 2005
- 136
-
Average Case Analysis for Tree Labelling SchemesKao, Ming-Yang / Li, Xiang-Yang / Wang, WeiZhao et al. | 2005
- 146
-
Revisiting T. Uno and M. Yagiura’s AlgorithmXuan, Binh-Minh Bui / Habib, Michel / Paul, Christophe et al. | 2005
- 156
-
Generating Cut Conjunctions and Bridge Avoiding Extensions in GraphsKhachiyan, L. / Boros, E. / Borys, K. / Elbassioni, K. / Gurvich, V. / Makino, K. et al. | 2005
- 166
-
Orthogonal Drawings of Series-Parallel Graphs with Minimum BendsZhou, Xiao / Nishizeki, Takao et al. | 2005
- 176
-
Bisecting a Four-Connected Graph with Three Resource SetsIshii, Toshimasa / Iwata, Kengo / Nagamochi, Hiroshi et al. | 2005
- 186
-
Laminar Structure of Ptolemaic Graphs and Its ApplicationsUehara, Ryuhei / Uno, Yushi et al. | 2005
- 196
-
On the Complexity of the G-Reconstruction ProblemDvořák, Zdeněk / Jelínek, Vít et al. | 2005
- 206
-
Hybrid Voting Protocols and Hardness of ManipulationElkind, Edith / Lipmaa, Helger et al. | 2005
- 216
-
On the Complexity of Rocchio’s Similarity-Based Relevance Feedback AlgorithmChen, Zhixiang / Fu, Bin et al. | 2005
- 226
-
Correlation Clustering and Consensus ClusteringBonizzoni, Paola / Vedova, Gianluca / Dondi, Riccardo / Jiang, Tao et al. | 2005
- 236
-
An Approximation Algorithm for Scheduling Malleable Tasks Under General Precedence ConstraintsJansen, Klaus / Zhang, Hu et al. | 2005
- 246
-
A 1.5-Approximation of the Minimal Manhattan Network ProblemSeibert, Sebastian / Unger, Walter et al. | 2005
- 256
-
Hardness and Approximation of Octilinear Steiner TreesMüller-Hannemann, Matthias / Schulze, Anna et al. | 2005
- 266
-
Dense Subgraph Problems with Output-Density ConditionsSuzuki, Akiko / Tokuyama, Takeshi et al. | 2005
- 277
-
A Complete Characterization of Tolerable Adversary Structures for Secure Point-to-Point Transmissions Without FeedbackDesmedt, Yvo / Wang, Yongge / Burmester, Mike et al. | 2005
- 288
-
Network Game with Attacker and Protector EntitiesMavronicolas, Marios / Papadopoulou, Vicky / Philippou, Anna / Spirakis, Paul et al. | 2005
- 298
-
SkipTree: A Scalable Range-Queryable Distributed Data Structure for Multidimensional DataAlaei, Saeed / Toossi, Mohammad / Ghodsi, Mohammad et al. | 2005
- 308
-
The Phase MatrixHøyer, Peter et al. | 2005
- 318
-
ISB-Tree: A New Indexing Scheme with Efficient Expected BehaviourKaporis, Alexis / Makris, Christos / Mavritsakis, George / Sioutas, Spyros / Tsakalidis, Athanasios / Tsichlas, Kostas / Zaroliagis, Christos et al. | 2005
- 328
-
External Data Structures for Shortest Path Queries on Planar DigraphsArge, Lars / Toma, Laura et al. | 2005
- 339
-
Improved Approximate String Matching Using Compressed Suffix Data StructuresLam, Tak-Wah / Sung, Wing-Kin / Wong, Swee-Seong et al. | 2005
- 349
-
Monitoring Continuous Band-Join Queries over Dynamic DataAgarwal, Pankaj K. / Xie, Junyi / Yang, Jun / Yu, Hai et al. | 2005
- 360
-
Approximate Colored Range QueriesLai, Ying Kit / Poon, Chung Keung / Shi, Benyun et al. | 2005
- 370
-
Complexity and Approximation of the Minimum Recombination Haplotype Configuration ProblemLiu, Lan / Chen, Xi / Xiao, Jing / Jiang, Tao et al. | 2005
- 380
-
Space Efficient Algorithms for Ordered Tree ComparisonWang, Lusheng / Zhang, Kaizhong et al. | 2005
- 392
-
A 1.75-Approximation Algorithm for Unsigned Translocation DistanceCui, Yun / Wang, Lusheng / Zhu, Daming et al. | 2005
- 402
-
Fast Algorithms for Computing the Tripartition-Based Distance Between Phylogenetic NetworksNguyen, Nguyen Bao / Nguyen, C. Thach / Sung, Wing-Kin et al. | 2005
- 412
-
Improved Algorithms for Largest Cardinality 2-Interval Pattern ProblemYuan, Hao / Yang, Linji / Chen, Erdong et al. | 2005
- 422
-
Preemptive Semi-online Scheduling on Parallel Machines with Inexact Partial InformationHe, Yong / Jiang, Yiwei et al. | 2005
- 433
-
On-Line Computation and Maximum-Weighted Hereditary Subgraph ProblemsDemange, Marc / Kouakou, Bernard / Soutif, Éric et al. | 2005
- 443
-
A Novel Adaptive Learning Algorithm for Stock Market PredictionYu, Lean / Wang, Shouyang / Lai, Kin Keung et al. | 2005
- 453
-
Uniformization of Discrete DataYang, Lei et al. | 2005
- 463
-
A Practical Algorithm for the Computation of Market Equilibrium with Logarithmic Utility FunctionsHuang, Li-Sha et al. | 2005
- 473
-
Boosting Spectral Partitioning by Sampling and IterationGiesen, Joachim / Mitsche, Dieter et al. | 2005
- 483
-
Smoothed Analysis of Binary Search TreesManthey, Bodo / Reischuk, Rüdiger et al. | 2005
- 493
-
Simple and Efficient Greedy Algorithms for Hamilton Cycles in Random Intersection GraphsRaptopoulos, C. / Spirakis, P. et al. | 2005
- 505
-
Counting Distinct Items over Update StreamsGanguly, Sumit et al. | 2005
- 515
-
Randomized Algorithm for the Sum Selection ProblemLin, Tien-Ching / Lee, D. T. et al. | 2005
- 524
-
An Improved Interval Routing Scheme for Almost All Networks Based on Dominating CliquesNehéz, Martin / Olejár, Daniel et al. | 2005
- 533
-
Basic Computations in Wireless NetworksCaragiannis, Ioannis / Galdi, Clemente / Kaklamanis, Christos et al. | 2005
- 543
-
A Simple Optimal Randomized Algorithm for Sorting on the PDMRajasekaran, Sanguthevar / Sen, Sandeep et al. | 2005
- 553
-
Efficient Parallel Algorithms for Constructing a k-Tree Center and a k-Tree Core of a Tree NetworkWang, Yan / Wang, Deqiang / Liu, Wei / Tian, Baoyu et al. | 2005
- 563
-
A Tight Bound on the Number of Mobile Servers to Guarantee the Mutual Transferability Among Dominating ConfigurationsFujita, Satoshi et al. | 2005
- 573
-
Bounding the Number of Minimal Dominating Sets: A Measure and Conquer ApproachFomin, Fedor V. / Grandoni, Fabrizio / Pyatkin, Artem V. / Stepanov, Alexey A. et al. | 2005
- 583
-
Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-Width, or Clique-WidthDragan, Feodor F. / Yan, Chenyu et al. | 2005
- 593
-
Sampling Unlabeled Biconnected Planar GraphsBodirsky, Manuel / Gröpl, Clemens / Kang, Mihyun et al. | 2005
- 604
-
Configurations with Few Crossings in Topological GraphsKnauer, Christian / Schramm, Étienne / Spillner, Andreas / Wolff, Alexander et al. | 2005
- 614
-
On Bounded Load Routings for Modeling k-Regular Connection TopologiesKosowski, Adrian / Małafiejski, Michał / Żyliński, Paweł et al. | 2005
- 624
-
On the Complexity of Global Constraint SatisfactionBazgan, Cristina / Karpinski, Marek et al. | 2005
- 634
-
Polynomial Space Suffices for Deciding Nash Equilibria Properties for Extensive Games with Large Trees,Àlvarez, Carme / Gabarró, Joaquim / Serna, Maria et al. | 2005
- 644
-
An Improved $\tilde{\mathcal{O}}(1.234^{m})$ -Time Deterministic Algorithm for SATYamamoto, Masaki et al. | 2005
- 654
-
Solving Minimum Weight Exact Satisfiability in Time O(20.2441n )Porschen, Stefan et al. | 2005
- 665
-
Efficient Algorithms for Finding a Longest Common Increasing SubsequenceChan, Wun-Tat / Zhang, Yong / Fung, Stanley P. Y. / Ye, Deshi / Zhu, Hong et al. | 2005
- 675
-
Decision Making Based on Approximate and Smoothed Pareto CurvesAckermann, Heiner / Newman, Alantha / Röglin, Heiko / Vöcking, Berthold et al. | 2005
- 685
-
Computing Optimal Solutions for the min 3-set covering ProblemCroce, Federico / Paschos, Vangelis Th. et al. | 2005
- 693
-
Efficient Algorithms for the Weighted 2-Center Problem in a Cactus GraphBen-Moshe, Boaz / Bhattacharya, Binay / Shi, Qiaosheng et al. | 2005
- 704
-
Algorithms for Local Forest SimilarityPeng, Zeshan et al. | 2005
- 714
-
Fast Algorithms for Finding Disjoint Subsequences with Extremal DensitiesBergkvist, Anders / Damaschke, Peter et al. | 2005
- 724
-
A Polynomial Space and Polynomial Delay Algorithm for Enumeration of Maximal Motifs in a SequenceArimura, Hiroki / Uno, Takeaki et al. | 2005
- 738
-
5-th Phylogenetic Root Construction for Strictly Chordal GraphsKennedy, William / Lin, Guohui et al. | 2005
- 748
-
Recursion Theoretic Operators for Function Complexity ClassesUeno, Kenya et al. | 2005
- 757
-
From Balls and Bins to Points and VerticesKlasing, Ralf / Lotker, Zvi / Navarra, Alfredo / Perennes, Stephane et al. | 2005
- 767
-
Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGsLu, Pinyan / Zhang, Jialin / Poon, Chung Keung / Cai, Jin-Yi et al. | 2005
- 777
-
Upper Bounds on the Computational Power of an Optical Model of ComputationWoods, Damien et al. | 2005
- 789
-
Complexity of the Min-Max (Regret) Versions of Cut ProblemsAissi, Hassene / Bazgan, Cristina / Vanderpooten, Daniel et al. | 2005
- 799
-
Improved Algorithms for the k Maximum-Sums ProblemsCheng, Chih-Huai / Chen, Kuan-Yu / Tien, Wen-Chin / Chao, Kun-Mao et al. | 2005
- 809
-
Network Load GamesCaragiannis, Ioannis / Galdi, Clemente / Kaklamanis, Christos et al. | 2005
- 819
-
Minimum Entropy ColoringCardinal, Jean / Fiorini, Samuel / Joret, Gwenaël et al. | 2005
- 829
-
Algorithms for Max Hamming Exact SatisfiabilityDahllöf, Vilhelm et al. | 2005
- 839
-
Counting Stable Strategies in Random Evolutionary GamesKontogiannis, Spyros / Spirakis, Paul et al. | 2005
- 849
-
Exact and Approximation Algorithms for Computing the Dilation Spectrum of Paths, Trees, and CyclesKlein, Rolf / Knauer, Christian / Narasimhan, Giri / Smid, Michiel et al. | 2005
- 859
-
On the Computation of Colored Domino Tilings of Simple and Non-simple Orthogonal PolygonsWorman, Chris / Yang, Boting et al. | 2005
- 869
-
Optimal Paths for Mutually Visible AgentsFenwick, Joel / Estivill-Castro, V. et al. | 2005
- 882
-
Stacking and Bundling Two Convex PolygonsAhn, Hee-Kap / Cheong, Otfried et al. | 2005
- 892
-
Algorithms for Range-Aggregate Query Problems Involving Geometric Aggregation OperationsGupta, Prosenjit et al. | 2005
- 902
-
A ( $2 - c{{1} \over {\sqrt{N}}}$ )–Approximation Algorithm for the Stable Marriage ProblemIwama, Kazuo / Miyazaki, Shuichi / Yamauchi, Naoya et al. | 2005
- 915
-
Approximating the Traffic Grooming ProblemFlammini, Michele / Moscardelli, Luca / Shalom, Mordechai / Zaks, Shmuel et al. | 2005
- 925
-
Scheduling to Minimize Makespan with Time-Dependent Processing TimesKang, L. Y. / Cheng, T. C. E. / Ng, C. T. / Zhao, M. et al. | 2005
- 934
-
On Complexity and Approximability of the Labeled Maximum/Perfect Matching ProblemsMonnot, Jérôme et al. | 2005
- 944
-
Finding a Weight-Constrained Maximum-Density Subtree in a TreeHsieh, Sun-Yuan / Chou, Ting-Yu et al. | 2005
- 954
-
Finding Two Disjoint Paths in a Network with Normalized α + -MIN-SUM Objective FunctionYang, Bing / Zheng, S. Q. / Lu, Enyue et al. | 2005
- 964
-
Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann TimePettie, Seth et al. | 2005
- 974
-
Approximation Algorithms for Layered Multicast SchedulingCai, Qingbo / Liberatore, Vincenzo et al. | 2005
- 984
-
Minimum Weight Triangulation by Cutting Out TrianglesGrantson, Magdalene / Borgelt, Christian / Levcopoulos, Christos et al. | 2005
- 995
-
Multi-directional Width-Bounded Geometric Separator and Protein FoldingFu, Bin / Oprisan, Sorinel A / Xu, Lizhe et al. | 2005
- 1007
-
Shortest Paths and Voronoi Diagrams with Transportation Networks Under General DistancesBae, Sang Won / Chwa, Kyung-Yong et al. | 2005
- 1019
-
Approximation Algorithms for Computing the Earth Mover’s Distance Under TransformationsKlein, Oliver / Veltkamp, Remco C. et al. | 2005
- 1029
-
Fast k-Means Algorithms with Constant ApproximationSong, Mingjun / Rajasekaran, Sanguthevar et al. | 2005
- 1039
-
On Efficient Weighted Rectangle Packing with Large ResourcesFishkin, Aleksei V. / Gerber, Olga / Jansen, Klaus et al. | 2005
- 1051
-
On Routing in VLSI Design and Communication NetworksTerlaky, Tamás / Vannelli, Anthony / Zhang, Hu et al. | 2005
- 1061
-
The Capacitated Traveling Salesman Problem with Pickups and Deliveries on a TreeLim, Andrew / Wang, Fan / Xu, Zhou et al. | 2005
- 1071
-
Distance Labeling in Hyperbolic GraphsGavoille, Cyril / Ly, Olivier et al. | 2005
- 1080
-
Multi-source Trees: Algorithms for Minimizing Eccentricity Cost MetricsFragopoulou, Paraskevi / Nikolopoulos, Stavros D. / Palios, Leonidas et al. | 2005
- 1090
-
Edge-Pancyclicity of Twisted CubesFan, Jianxi / Lin, Xiaola / Jia, Xiaohua / Lau, Rynson W. H. et al. | 2005
- 1100
-
Combinatorial Network Abstraction by Trees and DistancesEckhardt, Stefan / Kosub, Sven / Maaß, Moritz G. / Täubig, Hanjo / Wernicke, Sebastian et al. | 2005
- 1110
-
Drawing Phylogenetic TreesBachmaier, Christian / Brandes, Ulrik / Schlieper, Barbara et al. | 2005
- 1122
-
Localized and Compact Data-Structure for Comparability GraphsBazzaro, Fabrice / Gavoille, Cyril et al. | 2005
- 1132
-
Representation of Graphs by OBDDsNunkesser, Robin / Woelfel, Philipp et al. | 2005
- 1143
-
Space-Efficient Construction of LZ-IndexArroyuelo, Diego / Navarro, Gonzalo et al. | 2005
- 1153
-
Longest Increasing Subsequences in Windows Based on Canonical Antichain PartitionChen, Erdong / Yuan, Hao / Yang, Linji et al. | 2005
- 1163
-
Pareto Optimality in House Allocation ProblemsAbraham, David J. / Cechlárová, Katarína / Manlove, David F. / Mehlhorn, Kurt et al. | 2005
- 1176
-
Generalized Geometric Approaches for Leaf Sequencing Problems in Radiation Therapy,Chen, Danny Z. / Hu, Xiaobo S. / Luan, Shuang / Naqvi, Shahid A. / Wang, Chao / Yu, Cedric X. et al. | 2005