Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Automata, Languages and Programming [[electronic resource] ] : 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings / / edited by Jos C.M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger
| Automata, Languages and Programming [[electronic resource] ] : 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings / / edited by Jos C.M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger |
| Edizione | [1st ed. 2003.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 |
| Descrizione fisica | 1 online resource (XXXVI, 1199 p.) |
| Disciplina | 005.1 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Software engineering
Computers Computer communication systems Data structures (Computer science) Computer science—Mathematics Software Engineering/Programming and Operating Systems Theory of Computation Computer Communication Networks Data Structures Mathematics of Computing |
| ISBN | 3-540-45061-0 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Lectures -- Polarized Process Algebra and Program Equivalence -- Problems on RNA Secondary Structure Prediction and Design -- Some Issues Regarding Search, Censorship, and Anonymity in Peer to Peer Networks -- The SPQR-Tree Data Structure in Graph Drawing -- Model Checking and Testing Combined -- Logic and Automata: A Match Made in Heaven -- Algorithms -- Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes -- Generalized Framework for Selectors with Applications in Optimal Group Testing -- Decoding of Interleaved Reed Solomon Codes over Noisy Data -- Process Algebra -- On the Axiomatizability of Ready Traces, Ready Simulation, and Failure Traces -- Resource Access and Mobility Control with Dynamic Privileges Acquisition -- Replication vs. Recursive Definitions in Channel Based Calculi -- Approximation Algorithms -- Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem -- An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality -- An Improved Approximation Algorithm for Vertex Cover with Hard Capacities -- Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem -- Approximating Steiner k-Cuts -- MAX k-CUT and Approximating the Chromatic Number of Random Graphs -- Approximation Algorithm for Directed Telephone Multicast Problem -- Languages and Programming -- Mixin Modules and Computational Effects -- Decision Problems for Language Equations with Boolean Operations -- Generalized Rewrite Theories -- Complexity -- Sophistication Revisited -- Scaled Dimension and Nonuniform Complexity -- Quantum Search on Bounded-Error Inputs -- A Direct Sum Theorem in Communication Complexity via Message Compression -- Data Structures -- Optimal Cache-Oblivious Implicit Dictionaries -- The Cell Probe Complexity of Succinct Data Structures -- Succinct Representations of Permutations -- Succinct Dynamic Dictionaries and Trees -- Graph Algorithms -- Labeling Schemes for Weighted Dynamic Trees -- A Simple Linear Time Algorithm for Computing a (2k — 1)-Spanner of O(n 1+1/k ) Size in Weighted Graphs -- Multicommodity Flows over Time: Efficient Algorithms and Complexity -- Multicommodity Demand Flow in a Tree -- Automata -- Skew and Infinitary Formal Power Series -- Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser’s Separation -- Residual Languages and Probabilistic Automata -- A Testing Scenario for Probabilistic Automata -- The Equivalence Problem for t-Turn DPDA Is Co-NP -- Flip-Pushdown Automata: k + 1 Pushdown Reversals Are Better than k -- Optimization and Games -- Convergence Time to Nash Equilibria -- Nashification and the Coordination Ratio for a Selfish Routing Game -- Stable Marriages with Multiple Partners: Efficient Search for an Optimal Solution -- An Intersection Inequality for Discrete Distributions and Related Generation Problems -- Graphs and Bisimulation -- Higher Order Pushdown Automata, the Caucal Hierarchy of Graphs and Parity Games -- Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes -- Bisimulation Proof Methods for Mobile Ambients -- On Equivalent Representations of Infinite Structures -- Online Problems -- Adaptive Raising Strategies Optimizing Relative Efficiency -- A Competitive Algorithm for the General 2-Server Problem -- On the Competitive Ratio for Online Facility Location -- A Study of Integrated Document and Connection Caching -- Verification -- A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems -- Monadic Second-Order Logics with Cardinalities -- ? 2 ? ? 2 ? AFMC -- Upper Bounds for a Theory of Queues -- Around the Internet -- Degree Distribution of the FKP Network Model -- Similarity Matrices for Pairs of Graphs -- Algorithmic Aspects of Bandwidth Trading -- Temporal Logic and Model Checking -- CTL+ Is Complete for Double Exponential Time -- Hierarchical and Recursive State Machines with Context-Dependent Properties -- Oracle Circuits for Branching-Time Model Checking -- Graph Problems -- There Are Spanning Spiders in Dense Graphs (and We Know How to Find Them) -- The Computational Complexity of the Role Assignment Problem -- Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs -- Genus Characterizes the Complexity of Graph Problems: Some Tight Results -- Logic and Lambda-Calculus -- The Definition of a Temporal Clock Operator -- Minimal Classical Logic and Control Operators -- Counterexample-Guided Control -- Axiomatic Criteria for Quotients and Subobjects for Higher-Order Data Types -- Data Structures and Algorithms -- Efficient Pebbling for List Traversal Synopses -- Function Matching: Algorithms, Applications, and a Lower Bound -- Simple Linear Work Suffix Array Construction -- Types and Categories -- Expansion Postponement via Cut Elimination in Sequent Calculi for Pure Type Systems -- Secrecy in Untrusted Networks -- Locally Commutative Categories -- Probabilistic Systems -- Semi-pullbacks and Bisimulations in Categories of Stochastic Relations -- Quantitative Analysis of Probabilistic Lossy Channel Systems -- Discounting the Future in Systems Theory -- Information Flow in Concurrent Games -- Sampling and Randomness -- Impact of Local Topological Information on Random Walks on Finite Graphs -- Analysis of a Simple Evolutionary Algorithm for Minimization in Euclidean Spaces -- Optimal Coding and Sampling of Triangulations -- Generating Labeled Planar Graphs Uniformly at Random -- Scheduling -- Online Load Balancing Made Simple: Greedy Strikes Back -- Real-Time Scheduling with a Budget -- Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling -- Anycasting in Adversarial Systems: Routing and Admission Control -- Geometric Problems -- Dynamic Algorithms for Approximating Interdistances -- Solving the Robots Gathering Problem. |
| Record Nr. | UNISA-996465893903316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Automata, Languages and Programming : 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings / / edited by Jos C.M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger
| Automata, Languages and Programming : 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings / / edited by Jos C.M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger |
| Edizione | [1st ed. 2003.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 |
| Descrizione fisica | 1 online resource (XXXVI, 1199 p.) |
| Disciplina | 005.1 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Software engineering
Computers Computer networks Data structures (Computer science) Computer science—Mathematics Software Engineering/Programming and Operating Systems Theory of Computation Computer Communication Networks Data Structures Mathematics of Computing |
| ISBN | 3-540-45061-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Lectures -- Polarized Process Algebra and Program Equivalence -- Problems on RNA Secondary Structure Prediction and Design -- Some Issues Regarding Search, Censorship, and Anonymity in Peer to Peer Networks -- The SPQR-Tree Data Structure in Graph Drawing -- Model Checking and Testing Combined -- Logic and Automata: A Match Made in Heaven -- Algorithms -- Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes -- Generalized Framework for Selectors with Applications in Optimal Group Testing -- Decoding of Interleaved Reed Solomon Codes over Noisy Data -- Process Algebra -- On the Axiomatizability of Ready Traces, Ready Simulation, and Failure Traces -- Resource Access and Mobility Control with Dynamic Privileges Acquisition -- Replication vs. Recursive Definitions in Channel Based Calculi -- Approximation Algorithms -- Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem -- An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality -- An Improved Approximation Algorithm for Vertex Cover with Hard Capacities -- Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem -- Approximating Steiner k-Cuts -- MAX k-CUT and Approximating the Chromatic Number of Random Graphs -- Approximation Algorithm for Directed Telephone Multicast Problem -- Languages and Programming -- Mixin Modules and Computational Effects -- Decision Problems for Language Equations with Boolean Operations -- Generalized Rewrite Theories -- Complexity -- Sophistication Revisited -- Scaled Dimension and Nonuniform Complexity -- Quantum Search on Bounded-Error Inputs -- A Direct Sum Theorem in Communication Complexity via Message Compression -- Data Structures -- Optimal Cache-Oblivious Implicit Dictionaries -- The Cell Probe Complexity of Succinct Data Structures -- Succinct Representations of Permutations -- Succinct Dynamic Dictionaries and Trees -- Graph Algorithms -- Labeling Schemes for Weighted Dynamic Trees -- A Simple Linear Time Algorithm for Computing a (2k — 1)-Spanner of O(n 1+1/k ) Size in Weighted Graphs -- Multicommodity Flows over Time: Efficient Algorithms and Complexity -- Multicommodity Demand Flow in a Tree -- Automata -- Skew and Infinitary Formal Power Series -- Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser’s Separation -- Residual Languages and Probabilistic Automata -- A Testing Scenario for Probabilistic Automata -- The Equivalence Problem for t-Turn DPDA Is Co-NP -- Flip-Pushdown Automata: k + 1 Pushdown Reversals Are Better than k -- Optimization and Games -- Convergence Time to Nash Equilibria -- Nashification and the Coordination Ratio for a Selfish Routing Game -- Stable Marriages with Multiple Partners: Efficient Search for an Optimal Solution -- An Intersection Inequality for Discrete Distributions and Related Generation Problems -- Graphs and Bisimulation -- Higher Order Pushdown Automata, the Caucal Hierarchy of Graphs and Parity Games -- Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes -- Bisimulation Proof Methods for Mobile Ambients -- On Equivalent Representations of Infinite Structures -- Online Problems -- Adaptive Raising Strategies Optimizing Relative Efficiency -- A Competitive Algorithm for the General 2-Server Problem -- On the Competitive Ratio for Online Facility Location -- A Study of Integrated Document and Connection Caching -- Verification -- A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems -- Monadic Second-Order Logics with Cardinalities -- ? 2 ? ? 2 ? AFMC -- Upper Bounds for a Theory of Queues -- Around the Internet -- Degree Distribution of the FKP Network Model -- Similarity Matrices for Pairs of Graphs -- Algorithmic Aspects of Bandwidth Trading -- Temporal Logic and Model Checking -- CTL+ Is Complete for Double Exponential Time -- Hierarchical and Recursive State Machines with Context-Dependent Properties -- Oracle Circuits for Branching-Time Model Checking -- Graph Problems -- There Are Spanning Spiders in Dense Graphs (and We Know How to Find Them) -- The Computational Complexity of the Role Assignment Problem -- Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs -- Genus Characterizes the Complexity of Graph Problems: Some Tight Results -- Logic and Lambda-Calculus -- The Definition of a Temporal Clock Operator -- Minimal Classical Logic and Control Operators -- Counterexample-Guided Control -- Axiomatic Criteria for Quotients and Subobjects for Higher-Order Data Types -- Data Structures and Algorithms -- Efficient Pebbling for List Traversal Synopses -- Function Matching: Algorithms, Applications, and a Lower Bound -- Simple Linear Work Suffix Array Construction -- Types and Categories -- Expansion Postponement via Cut Elimination in Sequent Calculi for Pure Type Systems -- Secrecy in Untrusted Networks -- Locally Commutative Categories -- Probabilistic Systems -- Semi-pullbacks and Bisimulations in Categories of Stochastic Relations -- Quantitative Analysis of Probabilistic Lossy Channel Systems -- Discounting the Future in Systems Theory -- Information Flow in Concurrent Games -- Sampling and Randomness -- Impact of Local Topological Information on Random Walks on Finite Graphs -- Analysis of a Simple Evolutionary Algorithm for Minimization in Euclidean Spaces -- Optimal Coding and Sampling of Triangulations -- Generating Labeled Planar Graphs Uniformly at Random -- Scheduling -- Online Load Balancing Made Simple: Greedy Strikes Back -- Real-Time Scheduling with a Budget -- Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling -- Anycasting in Adversarial Systems: Routing and Admission Control -- Geometric Problems -- Dynamic Algorithms for Approximating Interdistances -- Solving the Robots Gathering Problem. |
| Record Nr. | UNINA-9910144046403321 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Computer Science – Theory and Applications [[electronic resource] ] : 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings / / edited by Alexander S. Kulikov, Gerhard J. Woeginger
| Computer Science – Theory and Applications [[electronic resource] ] : 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings / / edited by Alexander S. Kulikov, Gerhard J. Woeginger |
| Edizione | [1st ed. 2016.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2016 |
| Descrizione fisica | 1 online resource (XXI, 425 p. 49 illus.) |
| Disciplina | 004 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Algorithms
Computer science—Mathematics Discrete mathematics Computer science Numerical analysis Machine theory Discrete Mathematics in Computer Science Theory of Computation Numerical Analysis Computer Science Logic and Foundations of Programming Formal Languages and Automata Theory |
| ISBN | 3-319-34171-5 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Algorithms and data structures -- Combinatorial optimization -- Constraint solving -- Computational complexity -- Cryptography -- Combinatorics in computer science -- Formal languages and automata -- Computational models and concepts -- Algorithms for concurrent and distributed systems, networks -- Proof theory and applications of logic to computer science -- Model checking -- Automated reasoning -- Deductive methods. |
| Record Nr. | UNISA-996465683003316 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2016 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Computer Science – Theory and Applications : 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings / / edited by Alexander S. Kulikov, Gerhard J. Woeginger
| Computer Science – Theory and Applications : 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings / / edited by Alexander S. Kulikov, Gerhard J. Woeginger |
| Edizione | [1st ed. 2016.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2016 |
| Descrizione fisica | 1 online resource (XXI, 425 p. 49 illus.) |
| Disciplina | 004 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Algorithms
Computer science—Mathematics Discrete mathematics Computer science Numerical analysis Machine theory Discrete Mathematics in Computer Science Theory of Computation Numerical Analysis Computer Science Logic and Foundations of Programming Formal Languages and Automata Theory |
| ISBN | 3-319-34171-5 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Algorithms and data structures -- Combinatorial optimization -- Constraint solving -- Computational complexity -- Cryptography -- Combinatorics in computer science -- Formal languages and automata -- Computational models and concepts -- Algorithms for concurrent and distributed systems, networks -- Proof theory and applications of logic to computer science -- Model checking -- Automated reasoning -- Deductive methods. |
| Record Nr. | UNINA-9910484339703321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2016 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Graph-Theoretic Concepts in Computer Science [[electronic resource] ] : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers / / edited by Hans L. Bodlaender, Gerhard J. Woeginger
| Graph-Theoretic Concepts in Computer Science [[electronic resource] ] : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers / / edited by Hans L. Bodlaender, Gerhard J. Woeginger |
| Edizione | [1st ed. 2017.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 |
| Descrizione fisica | 1 online resource (XIII, 440 p. 87 illus.) |
| Disciplina | 511.5 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science—Mathematics
Discrete mathematics Algorithms Artificial intelligence—Data processing Computer graphics Geometry Discrete Mathematics in Computer Science Data Science Computer Graphics |
| ISBN | 3-319-68705-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Contents -- Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions -- 1 Complex Networks and Random Graphs: A Motivation -- 2 Random Graphs and Real-World Networks -- 3 Random Graph Models as Null Models -- 3.1 Null Model 1: Uniform Random Graph -- 3.2 Null Model 2: Erdős-Rényi Random Graph with Fixed Number of Edges -- 3.3 Null Model 3: Fixing All Degrees and the Configuration Model -- 3.4 Small-World Properties of the Configuration Model -- 4 Extensions: Other Models -- References -- On Bubble Generators in Directed Graphs -- 1 Introduction -- 2 Preliminaries -- 3 The Bubble Generator -- 4 A Polynomial-Time Algorithm for Decomposing a Bubble -- 5 Conclusions and Open Problems -- References -- Critical Node Cut Parameterized by Treewidth and Solution Size is W[1]-Hard -- 1 Introduction -- 2 Preliminaries -- 3 W[1]-HardNess of SumCSP -- 4 W[1]-HardNess of CNC -- References -- Hierarchical Partial Planarity -- 1 Introduction -- 2 Preliminaries -- 3 Relationships to Other Planarity Problems -- 4 Biconnected Facial-Constrained Core Planarity -- 4.1 High-Level Description of the Algorithm -- 4.2 Detailed Description of the Algorithm -- 5 Open Problems -- References -- On the Relationship Between k-Planar and k-Quasi-Planar Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Edge Rerouting Operations and Proof Strategy -- 4 Removing Tangled (k+1)-Crossings -- 5 Removing Untangled (k+1)-Crossings -- 5.1 Obtaining (k+1)-Quasi-Planarity -- 5.2 Obtaining Simplicity -- 6 Conclusions and Open Problems -- References -- Extension Complexity of Stable Set Polytopes of Bipartite Graphs -- 1 Introduction -- 2 Rectangle Covers and Fooling Sets -- 3 An Improved Upper Bound -- 4 An Improved Lower Bound -- 5 A Small Rectangle Cover of the Special Entries -- References.
On the Number of Labeled Graphs of Bounded Treewidth -- 1 Introduction -- 2 The Construction -- 2.1 Notation and Definitions -- 2.2 Description of the Construction -- 2.3 Bounding the Treewidth -- 3 Proof of the Main Result -- 3.1 Number of Constructible Triples (, F, N) -- 3.2 Bounding the Number of Duplicates -- 3.3 Choosing the Parameter s -- 4 Concluding Remarks and Further Research -- References -- Uniquely Restricted Matchings and Edge Colorings -- 1 Introduction -- 2 Approximation Algorithms for Bipartite Graphs -- 3 Upper Bounds on ur'(G) -- 4 Concluding Remarks -- References -- Defective Coloring on Classes of Perfect Graphs -- 1 Introduction -- 2 Preliminaries and Definitions -- 3 NP-Hardness on Cographs -- 4 Polynomial Time Algorithm on Trivially Perfect Graphs -- 5 Algorithms on Cographs -- 5.1 Algorithm for Small Deficiency -- 5.2 Algorithm for Few Colors -- 5.3 Sub-Exponential Time Algorithm -- 6 Split and Chordal Graphs -- 6.1 Hardness for Bounded Deficiency -- 6.2 Hardness for Bounded Number of Colors -- 6.3 A Dynamic Programming Algorithm -- 7 Conclusions -- References -- Token Sliding on Chordal Graphs -- 1 Introduction -- 2 Hardness Results -- 2.1 Split Graphs -- 2.2 Bipartite Graphs -- 3 Interval Graphs -- 3.1 Basic Facts on Independent Sets in Interval Graphs -- 3.2 Reachability -- 3.3 Connectivity -- References -- Computing Maximum Cliques in B2-EPG Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Typed Intervals and Projection Graphs -- 3.1 Typed Intervals -- 3.2 Projection Graphs -- 4 Maximum Clique in B2-EPG Graphs -- 4.1 Graphs with Z-Vertices -- 4.2 General B2-EPG Graphs -- 5 Colorings and -boundedness -- References -- Intersection Graphs of Rays and Grounded Segments -- 1 Introduction -- 2 Preliminaries -- 3 Cycle Lemma -- 4 Stretchability -- 5 Rays and Segments -- References -- On H-Topological Intersection Graphs. 1 Introduction -- 2 Recognition of T-Graphs -- 3 Recognition Hardness -- 4 Dominating Set -- References -- The Hardness of Embedding Grids and Walls -- 1 Introduction -- 2 Preliminaries -- 2.1 From Homomorphism to Colored Embedding -- 3 Frames and Skeletons -- 4 Conclusions -- References -- Approximately Coloring Graphs Without Long Induced Paths -- 1 Introduction -- 2 Algorithm -- 3 Hardness Result -- 4 Conclusion -- References -- New and Simple Algorithms for Stable Flow Problems -- 1 Introduction -- 2 Preliminaries -- 3 A Polynomial-Time Augmenting Path Algorithm for Stable Flows -- 4 Stable Flows with Restricted Intervals -- 4.1 Forced Edges -- 4.2 Forbidden Edges -- 5 Stable Multicommodity Flows -- 5.1 Problem Simplification -- 5.2 Integral Multicommodity Stable Flows -- References -- Clique-Width and Well-Quasi-Ordering of Triangle-Free Graph Classes -- 1 Introduction -- 2 Preliminaries -- 3 Partitioning 3-Partite Graphs -- 4 Applications of Our Technique -- References -- Finding Cut-Vertices in the Square Roots of a Graph -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Contributions -- 2 Preliminaries -- 2.1 Squares and Powers of Graphs -- 2.2 Graph Decompositions -- 3 Basic Properties of the Atoms in a Square -- 4 Computation of the Cut-Vertices from the Square -- 4.1 Recognition of the Essential Cut-Vertices -- 4.2 Sufficient Conditions for Non Essential Cut-Vertices -- 5 Reconstructing the Block-Cut Tree of a Square Root -- 6 Application to Trees of Cycle-Powers -- 7 Conclusion -- References -- The Minimum Shared Edges Problem on Grid-Like Graphs -- 1 Introduction -- 2 Preliminaries -- 3 On Bounded and Holey Grids -- 3.1 Bounded Grids -- 3.2 Holey Grids -- 3.3 Manhattan-Like Acyclic Digraphs -- 4 The Nonexistence of Polynomial Kernels -- 5 Conclusion -- References -- Linearly -Bounding (P6,C4)-Free Graphs -- 1 Introduction. 2 Preliminaries -- 3 The Structure of (P6,C4)-Free Atoms -- 4 -Bounding (P6,C4)-Free Graphs -- 5 A 3/2-Approximation Algorithm -- References -- Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2 -- 1 Introduction -- 2 Preliminaries -- 3 Outerplanar Roots -- 3.1 Structural Lemmas -- 3.2 The Algorithm -- 4 Roots of Pathwidth at Most Two -- 5 Conclusions -- References -- Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Enumeration of Maximal Irredundant Sets for Chordal Graphs -- 4 Enumeration of Maximal Irredundant Sets for Interval Graphs -- 5 Conclusions -- References -- The Minimum Conflict-Free Row Split Problem Revisited -- 1 Introduction -- 2 Formulations in Terms of Branchings in Directed Acyclic Graphs -- 3 A Strengthening of Dilworth's Theorem and Its Connection to the MCRS Problem -- 3.1 A Min-Max Relation Strengthening Dilworth's Theorem -- 3.2 Connection with the MCRS Problem -- 4 (In)approximability Issues -- 4.1 Hardness Results -- 4.2 2-Approximating and via Laminar Set Families -- 4.3 Two Approximation Algorithms for Computing and -- 5 Conclusion -- References -- Drawing Planar Graphs with Few Geometric Primitives -- 1 Introduction -- 2 Trees with Segments on the Grid -- 3 Planar 3-Trees with Few Segments on the Grid -- 4 Maximal Outerplanar Graphs with Segments on the Grid -- 5 Triangulations and Planar Graphs with Circular Arcs -- References -- Mixed Dominating Set: A Parameterized Perspective -- 1 Introduction -- 2 Preliminaries -- 3 Algorithm for MDS Parameterized by the Solution Size -- 4 Outline of Algorithm for MDS Parameterized by Treewidth -- 5 Lower Bounds -- 6 Conclusion -- References -- Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity -- 1 Introduction -- 1.1 Related Work. 1.2 Our Contribution -- 2 Preliminaries -- 2.1 MSO and Its Extensions -- 2.2 Treewidth and Neighborhood Diversity -- 3 Graphs of Bounded Neighborhood Diversity -- 4 XP Algorithm for MSOGL on Bounded Treewidth -- 4.1 CSP, MSO and Treewidth -- 4.2 CSP Instance Construction -- 5 Conclusions -- References -- Extending Partial Representations of Trapezoid Graphs -- 1 Introduction -- 2 Modular Decomposition and Transitive Orientations -- 3 Trapezoid Models -- 4 Extending Partial Representations of Trapezoid Posets -- 5 Extending Partial Representations of Trapezoid Graphs -- References -- On Low Rank-Width Colorings -- 1 Introduction and Main Results -- 2 Preliminaries -- 3 Powers of Sparse Graphs -- 4 Other Positive Results -- 5 Negative Results -- 6 Erdős-Hajnal property and -boundedness -- 7 Conclusions -- References -- On Strongly Chordal Graphs That Are Not Leaf Powers -- 1 Introduction -- 2 Preliminary Notions -- 3 Alternating Cycles and Quartets in Leaf Powers -- 4 Strongly Chordal Graphs That Are Not Leaf Powers -- 5 Hardness of Finding rq in Chordal Graphs -- 6 Conclusion -- References -- New Results on Weighted Independent Domination -- 1 Introduction -- 2 Preliminaries -- 2.1 Modular Decomposition -- 2.2 Antineighborhood Decomposition -- 3 WID in (P5,P5)-Free Graphs -- 3.1 Decomposition Scheme -- 3.2 Application to (P5,P5)-Free Graphs -- 4 WID in (P5, P3+P2)-Free Graphs -- 5 Concluding Remarks and Open Problems -- References -- The Parameterized Complexity of the Equidomination Problem -- 1 Introduction -- 2 Twin Relation -- 3 Properties of Twin Classes Regarding Equidomination -- 4 An XP Algorithm for the k-EQUIDOMINATION Problem -- 5 Reduction Rules -- 6 Main Results -- 7 Hereditarily Equidominating Graphs -- 8 Conclusion and Outlook -- References -- Homothetic Triangle Contact Representations -- 1 Introduction -- 2 Schnyder Woods. 3 The System of Linear Equations. |
| Record Nr. | UNISA-996466470603316 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers / / edited by Hans L. Bodlaender, Gerhard J. Woeginger
| Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers / / edited by Hans L. Bodlaender, Gerhard J. Woeginger |
| Edizione | [1st ed. 2017.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 |
| Descrizione fisica | 1 online resource (XIII, 440 p. 87 illus.) |
| Disciplina | 511.5 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science—Mathematics
Discrete mathematics Algorithms Artificial intelligence—Data processing Computer graphics Geometry Discrete Mathematics in Computer Science Data Science Computer Graphics |
| ISBN | 3-319-68705-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Contents -- Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions -- 1 Complex Networks and Random Graphs: A Motivation -- 2 Random Graphs and Real-World Networks -- 3 Random Graph Models as Null Models -- 3.1 Null Model 1: Uniform Random Graph -- 3.2 Null Model 2: Erdős-Rényi Random Graph with Fixed Number of Edges -- 3.3 Null Model 3: Fixing All Degrees and the Configuration Model -- 3.4 Small-World Properties of the Configuration Model -- 4 Extensions: Other Models -- References -- On Bubble Generators in Directed Graphs -- 1 Introduction -- 2 Preliminaries -- 3 The Bubble Generator -- 4 A Polynomial-Time Algorithm for Decomposing a Bubble -- 5 Conclusions and Open Problems -- References -- Critical Node Cut Parameterized by Treewidth and Solution Size is W[1]-Hard -- 1 Introduction -- 2 Preliminaries -- 3 W[1]-HardNess of SumCSP -- 4 W[1]-HardNess of CNC -- References -- Hierarchical Partial Planarity -- 1 Introduction -- 2 Preliminaries -- 3 Relationships to Other Planarity Problems -- 4 Biconnected Facial-Constrained Core Planarity -- 4.1 High-Level Description of the Algorithm -- 4.2 Detailed Description of the Algorithm -- 5 Open Problems -- References -- On the Relationship Between k-Planar and k-Quasi-Planar Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Edge Rerouting Operations and Proof Strategy -- 4 Removing Tangled (k+1)-Crossings -- 5 Removing Untangled (k+1)-Crossings -- 5.1 Obtaining (k+1)-Quasi-Planarity -- 5.2 Obtaining Simplicity -- 6 Conclusions and Open Problems -- References -- Extension Complexity of Stable Set Polytopes of Bipartite Graphs -- 1 Introduction -- 2 Rectangle Covers and Fooling Sets -- 3 An Improved Upper Bound -- 4 An Improved Lower Bound -- 5 A Small Rectangle Cover of the Special Entries -- References.
On the Number of Labeled Graphs of Bounded Treewidth -- 1 Introduction -- 2 The Construction -- 2.1 Notation and Definitions -- 2.2 Description of the Construction -- 2.3 Bounding the Treewidth -- 3 Proof of the Main Result -- 3.1 Number of Constructible Triples (, F, N) -- 3.2 Bounding the Number of Duplicates -- 3.3 Choosing the Parameter s -- 4 Concluding Remarks and Further Research -- References -- Uniquely Restricted Matchings and Edge Colorings -- 1 Introduction -- 2 Approximation Algorithms for Bipartite Graphs -- 3 Upper Bounds on ur'(G) -- 4 Concluding Remarks -- References -- Defective Coloring on Classes of Perfect Graphs -- 1 Introduction -- 2 Preliminaries and Definitions -- 3 NP-Hardness on Cographs -- 4 Polynomial Time Algorithm on Trivially Perfect Graphs -- 5 Algorithms on Cographs -- 5.1 Algorithm for Small Deficiency -- 5.2 Algorithm for Few Colors -- 5.3 Sub-Exponential Time Algorithm -- 6 Split and Chordal Graphs -- 6.1 Hardness for Bounded Deficiency -- 6.2 Hardness for Bounded Number of Colors -- 6.3 A Dynamic Programming Algorithm -- 7 Conclusions -- References -- Token Sliding on Chordal Graphs -- 1 Introduction -- 2 Hardness Results -- 2.1 Split Graphs -- 2.2 Bipartite Graphs -- 3 Interval Graphs -- 3.1 Basic Facts on Independent Sets in Interval Graphs -- 3.2 Reachability -- 3.3 Connectivity -- References -- Computing Maximum Cliques in B2-EPG Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Typed Intervals and Projection Graphs -- 3.1 Typed Intervals -- 3.2 Projection Graphs -- 4 Maximum Clique in B2-EPG Graphs -- 4.1 Graphs with Z-Vertices -- 4.2 General B2-EPG Graphs -- 5 Colorings and -boundedness -- References -- Intersection Graphs of Rays and Grounded Segments -- 1 Introduction -- 2 Preliminaries -- 3 Cycle Lemma -- 4 Stretchability -- 5 Rays and Segments -- References -- On H-Topological Intersection Graphs. 1 Introduction -- 2 Recognition of T-Graphs -- 3 Recognition Hardness -- 4 Dominating Set -- References -- The Hardness of Embedding Grids and Walls -- 1 Introduction -- 2 Preliminaries -- 2.1 From Homomorphism to Colored Embedding -- 3 Frames and Skeletons -- 4 Conclusions -- References -- Approximately Coloring Graphs Without Long Induced Paths -- 1 Introduction -- 2 Algorithm -- 3 Hardness Result -- 4 Conclusion -- References -- New and Simple Algorithms for Stable Flow Problems -- 1 Introduction -- 2 Preliminaries -- 3 A Polynomial-Time Augmenting Path Algorithm for Stable Flows -- 4 Stable Flows with Restricted Intervals -- 4.1 Forced Edges -- 4.2 Forbidden Edges -- 5 Stable Multicommodity Flows -- 5.1 Problem Simplification -- 5.2 Integral Multicommodity Stable Flows -- References -- Clique-Width and Well-Quasi-Ordering of Triangle-Free Graph Classes -- 1 Introduction -- 2 Preliminaries -- 3 Partitioning 3-Partite Graphs -- 4 Applications of Our Technique -- References -- Finding Cut-Vertices in the Square Roots of a Graph -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Contributions -- 2 Preliminaries -- 2.1 Squares and Powers of Graphs -- 2.2 Graph Decompositions -- 3 Basic Properties of the Atoms in a Square -- 4 Computation of the Cut-Vertices from the Square -- 4.1 Recognition of the Essential Cut-Vertices -- 4.2 Sufficient Conditions for Non Essential Cut-Vertices -- 5 Reconstructing the Block-Cut Tree of a Square Root -- 6 Application to Trees of Cycle-Powers -- 7 Conclusion -- References -- The Minimum Shared Edges Problem on Grid-Like Graphs -- 1 Introduction -- 2 Preliminaries -- 3 On Bounded and Holey Grids -- 3.1 Bounded Grids -- 3.2 Holey Grids -- 3.3 Manhattan-Like Acyclic Digraphs -- 4 The Nonexistence of Polynomial Kernels -- 5 Conclusion -- References -- Linearly -Bounding (P6,C4)-Free Graphs -- 1 Introduction. 2 Preliminaries -- 3 The Structure of (P6,C4)-Free Atoms -- 4 -Bounding (P6,C4)-Free Graphs -- 5 A 3/2-Approximation Algorithm -- References -- Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2 -- 1 Introduction -- 2 Preliminaries -- 3 Outerplanar Roots -- 3.1 Structural Lemmas -- 3.2 The Algorithm -- 4 Roots of Pathwidth at Most Two -- 5 Conclusions -- References -- Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Enumeration of Maximal Irredundant Sets for Chordal Graphs -- 4 Enumeration of Maximal Irredundant Sets for Interval Graphs -- 5 Conclusions -- References -- The Minimum Conflict-Free Row Split Problem Revisited -- 1 Introduction -- 2 Formulations in Terms of Branchings in Directed Acyclic Graphs -- 3 A Strengthening of Dilworth's Theorem and Its Connection to the MCRS Problem -- 3.1 A Min-Max Relation Strengthening Dilworth's Theorem -- 3.2 Connection with the MCRS Problem -- 4 (In)approximability Issues -- 4.1 Hardness Results -- 4.2 2-Approximating and via Laminar Set Families -- 4.3 Two Approximation Algorithms for Computing and -- 5 Conclusion -- References -- Drawing Planar Graphs with Few Geometric Primitives -- 1 Introduction -- 2 Trees with Segments on the Grid -- 3 Planar 3-Trees with Few Segments on the Grid -- 4 Maximal Outerplanar Graphs with Segments on the Grid -- 5 Triangulations and Planar Graphs with Circular Arcs -- References -- Mixed Dominating Set: A Parameterized Perspective -- 1 Introduction -- 2 Preliminaries -- 3 Algorithm for MDS Parameterized by the Solution Size -- 4 Outline of Algorithm for MDS Parameterized by Treewidth -- 5 Lower Bounds -- 6 Conclusion -- References -- Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity -- 1 Introduction -- 1.1 Related Work. 1.2 Our Contribution -- 2 Preliminaries -- 2.1 MSO and Its Extensions -- 2.2 Treewidth and Neighborhood Diversity -- 3 Graphs of Bounded Neighborhood Diversity -- 4 XP Algorithm for MSOGL on Bounded Treewidth -- 4.1 CSP, MSO and Treewidth -- 4.2 CSP Instance Construction -- 5 Conclusions -- References -- Extending Partial Representations of Trapezoid Graphs -- 1 Introduction -- 2 Modular Decomposition and Transitive Orientations -- 3 Trapezoid Models -- 4 Extending Partial Representations of Trapezoid Posets -- 5 Extending Partial Representations of Trapezoid Graphs -- References -- On Low Rank-Width Colorings -- 1 Introduction and Main Results -- 2 Preliminaries -- 3 Powers of Sparse Graphs -- 4 Other Positive Results -- 5 Negative Results -- 6 Erdős-Hajnal property and -boundedness -- 7 Conclusions -- References -- On Strongly Chordal Graphs That Are Not Leaf Powers -- 1 Introduction -- 2 Preliminary Notions -- 3 Alternating Cycles and Quartets in Leaf Powers -- 4 Strongly Chordal Graphs That Are Not Leaf Powers -- 5 Hardness of Finding rq in Chordal Graphs -- 6 Conclusion -- References -- New Results on Weighted Independent Domination -- 1 Introduction -- 2 Preliminaries -- 2.1 Modular Decomposition -- 2.2 Antineighborhood Decomposition -- 3 WID in (P5,P5)-Free Graphs -- 3.1 Decomposition Scheme -- 3.2 Application to (P5,P5)-Free Graphs -- 4 WID in (P5, P3+P2)-Free Graphs -- 5 Concluding Remarks and Open Problems -- References -- The Parameterized Complexity of the Equidomination Problem -- 1 Introduction -- 2 Twin Relation -- 3 Properties of Twin Classes Regarding Equidomination -- 4 An XP Algorithm for the k-EQUIDOMINATION Problem -- 5 Reduction Rules -- 6 Main Results -- 7 Hereditarily Equidominating Graphs -- 8 Conclusion and Outlook -- References -- Homothetic Triangle Contact Representations -- 1 Introduction -- 2 Schnyder Woods. 3 The System of Linear Equations. |
| Record Nr. | UNINA-9910484501203321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Online Algorithms [[electronic resource] ] : The State of the Art / / edited by Amos Fiat, Gerhard J. Woeginger
| Online Algorithms [[electronic resource] ] : The State of the Art / / edited by Amos Fiat, Gerhard J. Woeginger |
| Edizione | [1st ed. 1998.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 1998 |
| Descrizione fisica | 1 online resource (XVIII, 436 p. 1 illus.) |
| Disciplina | 005.1 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Computer communication systems
Algorithms Computer programming Computer science—Mathematics Calculus of variations Computer Communication Networks Algorithm Analysis and Problem Complexity Programming Techniques Discrete Mathematics in Computer Science Calculus of Variations and Optimal Control; Optimization |
| ISBN | 3-540-68311-9 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Competitive analysis of algorithms -- Self-organizing data structures -- Competitive analysis of paging -- Metrical task systems, the server problem and the work function algorithm -- Distributed paging -- Competitive analysis of distributed algorithms -- On-line packing and covering problems -- On-line load balancing -- On-line scheduling -- On-line searching and navigation -- On-line network routing -- On-line network optimization problems -- Coloring graphs on-line -- On-Line Algorithms in Machine Learning -- Competitive solutions for on-line financial problems -- On the performance of competitive algorithms in practice -- Competitive odds and ends. |
| Record Nr. | UNISA-996466360503316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 1998 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Online Algorithms [[electronic resource] ] : The State of the Art / / edited by Amos Fiat, Gerhard J. Woeginger
| Online Algorithms [[electronic resource] ] : The State of the Art / / edited by Amos Fiat, Gerhard J. Woeginger |
| Edizione | [1st ed. 1998.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 1998 |
| Descrizione fisica | 1 online resource (XVIII, 436 p. 1 illus.) |
| Disciplina | 005.1 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Computer networks
Algorithms Computer programming Computer science—Mathematics Calculus of variations Computer Communication Networks Algorithm Analysis and Problem Complexity Programming Techniques Discrete Mathematics in Computer Science Calculus of Variations and Optimal Control; Optimization |
| ISBN | 3-540-68311-9 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Competitive analysis of algorithms -- Self-organizing data structures -- Competitive analysis of paging -- Metrical task systems, the server problem and the work function algorithm -- Distributed paging -- Competitive analysis of distributed algorithms -- On-line packing and covering problems -- On-line load balancing -- On-line scheduling -- On-line searching and navigation -- On-line network routing -- On-line network optimization problems -- Coloring graphs on-line -- On-Line Algorithms in Machine Learning -- Competitive solutions for on-line financial problems -- On the performance of competitive algorithms in practice -- Competitive odds and ends. |
| Record Nr. | UNINA-9910767579403321 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 1998 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||